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
Challenge
O(n) time.
public class Solution {
/**
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public int median(int[] nums) {
// write your code here
return quickSort(nums, 0, nums.length-1, (nums.length+1)/2);
}
private int quickSort(int[] nums, int i, int j, int k){
int start = i++;
while(i<=j){
while(i <= j && nums[i] < nums[start]) i++;
while(i <= j && nums[j] >= nums[start]) j--;
if(i < j)
swap(nums, i, j);
}
swap(nums, start, j);
if(k == j + 1) return nums[j];
else if(k > j + 1) return quickSort(nums, j+1, nums.length-1, k);
else {
return quickSort(nums, 0, j-1, k);
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
No comments:
Post a Comment