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.

http://www.lintcode.com/en/problem/median/

Discussion

Kth Largest Element问题的等价问题，如有nums.size()为even，k = nums.size()/2-1, 为odd，则k = nums.size()/2.

Solution

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: An integer denotes the middle number of the array.
     */
    int median(vector<int> &nums) {
        // write your code here
        if(nums.empty()) return -1;
        int med;
        if(nums.size() %2 == 0) {
            med = nums.size() / 2 - 1;
        } else {
            med = nums.size() / 2;
        }
        int start = 0;
        int end = nums.size() - 1;
        while(start <= end) {
            int pos = partition(nums, start, end);
            if(pos == med) {//find out median
                return nums[pos];
            } else if(pos > med) {//search in the first half
                end = pos -  1;
            } else { //serch in the second half
                start = pos + 1;
            }
        }
    }
    int partition(vector<int> &nums, int start, int end) {
        int pivot = nums[end];
        int i = start;//nums[0~i] <= pivot， i is the current postion where nums[i] <= pivot
        for(int j = start; j<end; j++) {
            if(nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[end]);
        return i;
    }
};

Folow up

如果nums是有序的，采用排序算法时间复杂度会提升到O(n^2)，一个解决办法是randomly generate the pivot

int partition(vector<int> &nums, int start, int end) {
        srand(time(NULL));
        int idx = rand()%(end-start+1) + start;//generate a random index for pivot
        int pivot = nums[idx];
        swap(nums[end], nums[idx]);
        int i = start;//nums[0~i] <= pivot， i is the current postion where nums[i] <= pivot
        for(int j = start; j<end; j++) {
            if(nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[end]);
        return i;
    }