Given a unsorted array with integers, find the median of it.
A median is the middle number of the array after it is sorted.
If there are even numbers in the array, return the N/2-th number after sorted.
Have you met this question in a real interview?
Yes
Example
Given [4, 5, 1, 2, 3], return 3
Given [7, 9, 4, 5], return 5
public int median(int[] nums) { int k = nums.length%2 == 0 ? nums.length/2-1 : nums.length/2; return helper(nums, 0, nums.length-1, k); } int helper(int[] nums, int left, int right, int k) { int pivot = right; int num = nums[pivot]; int low = left, high = right; while (low < high) { while (low < high && nums[low] < num) { low++; } while (low < high && nums[high] >= num) { high--; } swap(nums, low, high); } swap(nums, low, right); if (low == k) { return nums[low]; } else if (low < k) { return helper(nums, low+1, right, k); } else { return helper(nums, left, low-1, k); } } void swap(int[] num, int left, int right) { int tmp = num[left]; num[left] = num[right]; num[right] = tmp; }