215. Kth Largest Element in an Array

Find thekth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given[3,2,1,5,6,4]and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

S1: sort O(nlogn)

S2: quick select, partition

每次将数组分成两半，前一半小于pivot后一半大于pivot，若pivot index = n - k那么pivot就是所求，否则进行二分

best case: pivot选的很好每次都平均二分T(n) = T(n/2) + O(n), O(n)为partition复杂度，展开得到O(n+n/2+n/4+..+1) = O(n)

worst case: pivot选的很烂每次都是第一个或最后一个 T(n) = T(n-1) + O(n), 展开得到O(n+n-1+n-2+...1) = O(n^2)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left + 1 < right) {
            int mid = partition(nums, left, right);
            if (mid == n - k) {
                return nums[mid];
            } else if (mid < n - k) {
                left = mid + 1;  //这里partition的结果可能mid=left或right，需要加一避免死循环
            } else {
                right = mid - 1;
            }
        }
        return left == (n - k)? min(nums[left], nums[right]) : max(nums[left], nums[right]);
    }

private:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
};