【LeetCodeゼロブラシから】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 Sorting)のように、keyより大きい部分とkeyより小さい部分を毎回区別することです.
keyより小さい個数がKより大きい場合、keyより大きい部分は検索されません.keyより小さい個数がKより小さい場合、keyより大きい個数のうち(K−Kより小さい個数)より大きい数を探す.
このようにして、毎回の約半分の数字を探す必要がなく、時間の複雑さは約O(n+n/2+n/4+..+1)=O(2 n)=O(n)である.
最後に、高速ソート、二分ソートのように、二分(再帰)のサブ問題では中間要素を除去すべきである(範囲を縮小するたびに、範囲が変わらない死のサイクルを防ぐ).

class Solution {
public:
    void swap(int& a, int&b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        int head = 0;
        int tail = nums.size() - 1;
        int index = 0;
        
        while(head < tail) {
            while(nums[tail] <= nums[index] && head < tail) tail--;
            swap(nums[tail], nums[index]);
            index = tail;
            
            while(nums[head] >= nums[index] && head < tail) head++;
            swap(nums[head], nums[index]);
            index = head;
        }
        
        if(k == index + 1)  return nums[index];
        else if(k < index + 1) {
            vector<int> sub(nums.begin(), nums.begin() + index);
            return findKthLargest(sub, k);
        }
        else if(k > index + 1) {
            vector<int> sub(nums.begin() + index + 1, nums.end());
            return findKthLargest(sub, k - index - 1);
        }
    }
};