题目
给定一个未排序的整数数组,找到其中位数。
中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。
http://www.lintcode.com/zh-cn/problem/median/
分析
将原来的数组排序,就能找到中位数。实际上,并不需要对数组进行完整排序,对于奇数个数的数组,中位数是排序后数组的第N/2个数,偶数则是第N/2-1个(根据题目要求)。我们只要找到一个数,比它小的数有N/2个,比它大的数有N/2-1个。至于比它小的部分和比它大的部分,乱序的也无所谓。这个过程非常类似快速排序法的分治过程,其流程可以描述为:
- 取一个数作为基数,将数组按照快速排序法的方式,把数组分成两部分,基数左边是比基数小的数,右边是比基数大的数
- 看基数当前的坐标,如果恰好就是目标坐标,说明基数就是中位数
- 若基数坐标小于中位数序号,说明中位数在基数右侧,递归查找右边
- 若基数坐标大于中位数坐标,说明中位数在基数左侧,递归查找左边
代码
public class Solution {
void swap(int[] nums, int ia, int ib){
if(ia == ib) return;
int temp = nums[ia];
nums[ia] = nums[ib];
nums[ib] = temp;
}
int qsort(int[] nums, int start, int end, int target) {
if(start == end && start == target){
return nums[target];
}
int pivot = nums[start];
int left = start, right = end;
for(;left < right;){
while(right > left && nums[right] >= pivot){
right--;
}
nums[left] = nums[right];
while(left < right && nums[left] <= pivot){
left++;
}
nums[right] = nums[left];
}
nums[right] = pivot;
if(right == target){
return nums[right];
}else if(right < target){
return qsort(nums, right+1, end, target);
}else{
return qsort(nums, start, right-1, target);
}
}
/*
* @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 qsort(nums, 0, nums.length - 1 ,
nums.length%2 == 1 ? (nums.length>>1) : (nums.length/2-1) );
}
}