LeetCode 215. Kth Largest Element in an Array

题目：https://leetcode.com/problems/kth-largest-element-in-an-array/
思路：
找第k大的元素，最简单的方法就是排个序，然后找一下（中位数其实也类似），时间复杂度是O(nlogn)
另一种方案是，参考快速排序的方法找个pivot，然后分三种情况：

• pivot的位置刚好就是第k大的，那么大功告成；
• pivot的位置在k前头，那么就得找pivot后面一堆了；
• pivot的位置在k后头，那么得找pivot前面的一堆；

代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return findKthLargest1(nums, 0, nums.size()-1, k);
    }
    int findKthLargest1(vector<int>& nums, int start, int end, int k) {
        int small = start;
        int large = end;
        int pivot = nums[large];
        while(true){
            while(nums[small] > pivot && small < large)
                small ++;
            while(nums[large] <=pivot && small < large)
                large --;
            if(small == large)
                break;
            swap(nums, small, large);
        }
        swap(nums, small, end);
        if(small == k - 1){
            return pivot;
        } else if (small > k - 1) {
            return findKthLargest1(nums, start, small - 1, k);
        } else {
            return findKthLargest1(nums, small + 1, end, k);
        }
    }
    void swap(vector<int>& nums, int small, int large) {
        int temp = nums[small];
        nums[small] = nums[large];
        nums[large] = temp;
    }
};