Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Find Median in Large File of Integers
//'main' method must be in a class 'Rextester'. //Compiler version 1.8.0_111 import java.util.*; import java.lang.*; class Rextester { public static void main(String args[]) { int[] nums = new int[100]; Random rand = new Random(); for (int i = 0; i < 100; i++) { int num = rand.nextInt(100); nums[i] = num; } Arrays.sort(nums); for (int i = 0; i < 100; i++) { System.out.print(nums[i] + ","); } System.out.println(nums[49]); System.out.println(nums[50]); System.out.println(findMedian(nums)); } // Find kth smallest number in sorted order private static int findKth(int[] nums, int k, int left, int right) { if (left >= right) return left; int guess = (int) (left + ((long) right - left) / 2); int count = 0, max = left, min = right; for (int num : nums) { if (num <= guess) { count++; max = Math.max(max, num); } else min = Math.min(min, num); } if (count == k) return max; else if (count < k) return findKth(nums, k, min, right); else return findKth(nums, k, left, max); } private static double findMedian(int[] nums) { int len = 0, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE; for (int num: nums) { len++; max = Math.max(max, num); min = Math.min(min, num); } if (len % 2 == 1) return (double) findKth(nums, len / 2 + 1, min, max); return (double) (findKth(nums, len / 2, min, max) + findKth(nums, len / 2 + 1, min, max)) / 2; } }
run
|
edit
|
history
|
help
0
2 dimensional array (filled in by the user)
true false
OBF-7 4
Write a program to sort the odd elements descending order and even elements in ascending order
isPrime
calc
LRU cache - Using doubly linked list (Fast!)
1(D)
Hi
Umang Khambhalikar