王争的快排分区方法真简洁

int Patition(vector<int>& v, int begin, int end) {
    int& pivot = v[end];
    int done = begin;
    for (int i = begin; i < end; ++i) {
        if (v[i] < pivot) {
            std::swap(v[i], v[done]);
            done++;
        }
    }
    std::swap(v[done], pivot);
    return done;
}

获得第几大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (k <= 0 || k > nums.size()) {
            throw "wrong input";
        }

        return findKthLargest(nums, 0, nums.size() - 1, k);
    }

    int findKthLargest(vector<int>& nums, int begin, int end, int k) {
        if (begin >= end)
            return nums[begin];

        int pivot = patition(nums, begin, end);
        if (pivot == k - 1) {
            return nums[pivot];
        } else if (pivot > k - 1) {
            return findKthLargest(nums, begin, pivot - 1, k);
        } else {
            return findKthLargest(nums, pivot + 1, end, k);
        }
    }

    int patition(vector<int>& nums, int begin, int end) {
        int rand_pos = begin + rand() % (end - begin + 1);
        if (rand_pos != end)
            std::swap(nums[end], nums[rand_pos]);

        int& pivot = nums[end];
        int done = begin;
        for (int i = begin; i < end; ++i) {
            if (nums[i] > pivot) {
                std::swap(nums[i], nums[done]);
                done++;
            }
        }

        std::swap(nums[done], pivot);
        return done;
    }
};