找中位数

题目

给定一个未排序的整数数组,找到其中位数。
中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第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) );  
        
    }
}
Show Comments

Get the latest posts delivered right to your inbox.