We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Find the Median
  5. Discussions

Find the Median

  • sgrphw
     + 3 comments

    if observed carefully N (array size i.e. 1000000) is grater than X (Range of array elements i.e. -10000<= A[i] <= 10000). so i will suggest count sort. always gives complexity(O(X)) = 1/2* O(X).

    saves a lot of time..

    import java.io.*;
import java.util.*;

public class Solution {
    public static int[] a;
    public static int[] c = new int[20001];
    public static int n;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
            c[a[i]+10000]++;
        }
        int s =0;
        outer:
        for(int i = 0; i < 20001; i++){
            s+=c[i];
            //System.out.print(i+" "+s+" ");
            if(s>n/2){
                System.out.print(i-10000);
                break outer;
            }
        }
    }
}