// 冒泡排序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 冒泡排序
        for(int i = 0; i < k; ++i)
        {
            for(int j = 1; j < nums.size(); ++j)
            {
                if(nums[j - 1] > nums[j])
                    swap(nums[j - 1], nums[j]);
            }
        }

        // 返回第 k 大的数字
        return *(nums.rbegin() + k - 1);
    }
};

// 堆排序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 初始化(默认大顶堆)
        priority_queue<int> heap(nums.begin(), nums.end());

        // 寻找第 k 大的元素
        k--;
        while(k--)
        {
            heap.pop();
        }

        return heap.top();
    }
};

// 快速选择：“模板题”
// 随机选择一个数，大的放左边，小的放右边。
class Solution {
public:
    int quick_select(vector<int>& nums, int l, int r, int k)
    {
        // 区间只有一个数的时候，直接返回
        if(l == r)
            return nums[l];

        // 随机选择一个数
        int num = nums[(l + r) >> 1];
        int left = l - 1, right = r + 1;
        while(left < right)
        {
            // 大的放左边，小的放右边
            do left++; while(nums[left] > num);
            do right--; while(nums[right] < num);

            if(left < right)
                swap(nums[left], nums[right]);
        }

        // 左边数组的个数大于 k 
        if(right >= k)
            return quick_select(nums, l, right, k);
        else 
            return quick_select(nums, right + 1, r, k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        // 判断边界条件
        if(nums.size() == 0)
            return 0;

        // 快速选择(从 0 开始计数)
        return quick_select(nums, 0, nums.size() - 1, k - 1);
    }
};