[leetcode] 215. Kth Largest Element in an Array解題報告

タイトルリンク:https://leetcode.com/problems/kth-largest-element-in-an-array/
Find the kth 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.
構想:この問題はquick-selectのアルゴリズムを利用して、つまり急速に並べ替えたpartitionで、この方法の理論時間の複雑度はO(n)で、1種のとても役に立つツールです.
分割を使用して配列を2つのセグメントに分割し、分割点の位置を返します.この位置がちょうどk番目に大きい数であれば、この数を返します.
そうでなければ、戻る位置が探している位置より小さい場合は、右の半分の配列に向かって探し続けます.
戻る位置が探している位置より大きい場合は、左側に探します.
コードは次のとおりです.

class Solution {
public:
    int findKth(vector<int>& nums, int low, int high)
    {
        int val = nums[high], k = low-1;
        for(int i = low; i< nums.size(); i++)
            if(nums[i] < val) 
                swap(nums[++k], nums[i]);
        swap(nums[high], nums[++k]);
        return k;
    }
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size(), low = 0, high = len-1, pos=-1;
        while(low <= high)
        {
            pos = findKth(nums, low, high);
            if(pos == len-k) return nums[pos];
            else if(pos > len-k) high = pos-1;
            else if(pos < len-k) low = pos+1;
        }
    }
};