题目

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