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)); System.out.println(findMedian2(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; } private static double findMedian2(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); } return findMedianHelper(nums, min, max); } private static double findMedianHelper(int[] nums, int lo, int hi) { while (lo < hi) { int mid = (int) ((long) lo + hi) / 2; int len = 0, count = 0; int max = lo, min = hi; for (int num : nums) { len++; if (num <= mid) { count++; max = Math.max(max, num); } else min = Math.min(min, num); } if (count == (len + 1) / 2) return len % 2 == 1 ? max : 0.5*((double) max + min); else if (count > (len + 1) / 2) hi = max; else lo = min; } return lo; } }
run
|
edit
|
history
|
help
0
JAVA regex for only allow numbers
rta
ArrayOperation
bit right 2
Question FizzBuzz
String Palindrome
detect cycle in singly linked list
Aaina
Ridhiverma
different ways to add parenthesis leetcode #241