w3resource

Java Exercises: Find the median of the number inside the window

Java Basic: Exercise-173 with Solution

Write a Java program to find the median of the number inside the window (size k) at each moving in a given array of integers with duplicate numbers. Move the window from the start of the array.

{|1, 2, 3|, 4, 5, 6, 7, 8, 8} -> Return median 2
{1, |2, 3, 4|, 5, 6, 7, 8, 8} -> Return median 3
{1, 2, |3, 4, 5|, 6, 7, 8, 8} -> Return median 4
{1, 2, 3, |4, 5, 6|, 7, 8, 8} -> Return median 5
{1, 2, 3, 4, |5, 6, 7|, 8, 8} -> Return median 6
{1, 2, 3, 4, 5, |6, 7, 8|, 8} -> Return median 7
{1, 2, 3, 4, 5, 6, |7, 8, 8|} -> Return median 8
Result array {2, 3, 4, 5, 6, 7, 8}

Sample Solution:

Java Code:

import java.util.*;
import java.util.Arrays;
import java.util.LinkedList;

public class Solution {
 public static void main(String[] args) {
  int[] main_array = {1, 2, 3, 4, 5, 6, 7, 8, 8};
  int k = 3;
  System.out.println("\nOriginal array: " + Arrays.toString(main_array));
  System.out.println("\nValue of k: " + k);
  System.out.println("\nResult: ");
  ArrayList < Integer > result = median_slide_window(main_array, k);
  for (int i = 0; i < result.size(); i++) {
   System.out.println(result.get(i));
  }
 }
 public static ArrayList < Integer > median_slide_window(int[] main_array, int k) {
  ArrayList < Integer > result = new ArrayList < > ();
  if (k == 0 || main_array.length < k) {
   return result;
  }
  PriorityQueue < Integer > right_num = new PriorityQueue < Integer > (k);
  PriorityQueue < Integer > left_num = new PriorityQueue < Integer > (k, Collections.reverseOrder());

  for (int i = 0; i < k - 1; ++i) {
   add(right_num, left_num, main_array[i]);
  }

  for (int i = k - 1; i < main_array.length; ++i) {
   add(right_num, left_num, main_array[i]);
   int median = compute_median(right_num, left_num);
   result.add(median);
   remove(right_num, left_num, main_array[i - k + 1]);
  }
  return result;
 }

 private static int compute_median(PriorityQueue < Integer > right_num, PriorityQueue < Integer > left_num) {
  if (left_num.isEmpty() && right_num.isEmpty()) {
   return 0;
  }
  while (left_num.size() < right_num.size()) {
   left_num.add(right_num.poll());
  }

  while (left_num.size() - right_num.size() > 1) {
   right_num.add(left_num.poll());
  }
  return left_num.peek();
 }

 private static void add(PriorityQueue < Integer > right_num, PriorityQueue < Integer > left_num, int num) {
  if (left_num.isEmpty() && right_num.isEmpty()) {
   left_num.add(num);
   return;
  } else {
   if (num <= compute_median(right_num, left_num)) {
    left_num.add(num);
   } else {
    right_num.add(num);
   }
  }
 }

 private static void remove(PriorityQueue < Integer > right_num, PriorityQueue < Integer > left_num, int num) {
  if (num <= compute_median(right_num, left_num)) {
   left_num.remove(num);
  } else {
   right_num.remove(num);
  }
 }
}

Sample Output:

Original array: [1, 2, 3, 4, 5, 6, 7, 8, 8]

Value of k: 3

Result: 
2
3
4
5
6
7
8

Pictorial Presentation:

Java exercises: Find the median of the number inside the window

Flowchart:

Flowchart: Java exercises: Find the median of the number inside the window.

Java Code Editor:

Company:  Google

Contribute your code and comments through Disqus.

Previous: Write a Java program to get the number of element in a given array of integers that are smaller than the integer of another given array of integers.
Next: Write a Java program to find the maximum number inside the number in the window (size k) at each moving in a given array of intergers with duplicate numbers. Move the window from the start of the array.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.

Java: Tips of the Day

Java: Anagrams

Generates all anagrams of a string.

public static List<String> anagrams(String input) {
    if (input.length() <= 2) {
        return input.length() == 2
                ? Arrays.asList(input, input.substring(1) + input.substring(0, 1))
                : Collections.singletonList(input);
    }
    return IntStream.range(0, input.length())
            .mapToObj(i -> new SimpleEntry<>(i, input.substring(i, i + 1)))
            .flatMap(entry ->
                    anagrams(input.substring(0, entry.getKey()) + input.substring(entry.getKey() + 1))
                            .stream()
                            .map(s -> entry.getValue() + s))
            .collect(Collectors.toList());
}

Ref: https://bit.ly/3rvAdAK