LintCode 80: Median (QuickSelect经典题)

80. Median

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.

Example
Example 1:

Input：[4, 5, 1, 2, 3]
Output：3
Explanation:
After sorting，[1,2,3,4,5]，the middle number is 3
Example 2:

Input：[7, 9, 4, 5]
Output：5
Explanation:
After sorting，[4,5,7,9]，the second(4/2) number is 5
Challenge
O(n) time.

Notice
The size of array is not exceed 10000

解法1：quickSelect。时间复杂度O(n)。
注意quickSelect里面当start>=end时是return nums[start]而不是nums[k]。
代码如下:

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    int median(vector<int> &nums) {
        int n = nums.size();
        vector<int> orignums;
        //int index = (n & 0x1) ? n / 2 + 1 : n / 2;
        return quickSelect(nums, 0, n - 1, (n + 1) / 2);
    }
private:
    int quickSelect(vector<int> &nums, int start, int end, int k) {
        if (start >= end) return nums[start]; //nums[k];
        int left = start, right = end;
        int pivot = nums[left + (right - left) / 2];
        while (left <= right) {
            while (left <= right && nums[left] < pivot) left++;
            while (left <= right && nums[right] > pivot) right--;
            if (left <= right) {
                swap(nums[left], nums[right]);
                left++;
                right--;
            }
        }
        if (start + k - 1 <= right)
            return quickSelect(nums, start, right, k);
        if (start + k - 1 >= left)
            return quickSelect(nums, left, end, k - (left - start));
        return pivot;
    }
};

解法2：MaxHeap
TBD

代码同步在
https://github.com/luqian2017/Algorithm