1. 描述: 为避免 P1177 那种 5000 个 5000 的数据, 本题我使用了三路快速选择, 就是把重复的值都归到数组中间去.
2. 说明: 暂时还没有随机化轴, 而是选择了左边界值作为轴.
3. 说明: 暂时还没有使用快读快写.
4. 超时记录: https://www.luogu.com.cn/record/62842077
5. 代码如下:

//三路快选
//P1923 (Luogu)
//LC0215 (LeetCode)

#include <vector>
using namespace std;
class Solution
{
public:
    static int ThreeWayRadixQuickSelect(vector<int> &nums, const int k, const int left, const int right)
    {
        if (left > right)
            return nums[left];
        int pivotIndex = left;
        int pivotValue = nums[pivotIndex];
        int l = left;
        int r = right - 1;
        int m = left + 1;
        while (m <= r)
        {
            if (nums[m] < pivotValue)
            {
                int temp = nums[m];
                nums[m] = nums[l+1];
                nums[l+1] = temp;
                l++;
                m++;
            }
            else if (nums[m] > pivotValue)
            {
                int temp = nums[m];
                nums[m] = nums[r];
                nums[r] = temp;
                r--;
            }
            else
            {
                m++;
            }
        }
        int temp = nums[l];
        nums[l] = nums[pivotIndex];
        nums[pivotIndex] = temp;
        if (k < l)
            return ThreeWayRadixQuickSelect(nums, k, left, l);
        else if (k > r)
            return ThreeWayRadixQuickSelect(nums, k, r+1, right);
        else
            return pivotValue;
    }
    int findKthLeast(vector<int> &nums, const int k)
    {
        return ThreeWayRadixQuickSelect(nums, k, 0, nums.size());
    }
    int findKthLargest(vector<int>& nums, int k)
    {
        return ThreeWayRadixQuickSelect(nums, nums.size()-k, 0, nums.size());
    }
};


#include <iostream>
using namespace std;
int main()
{
    int register n=0, k=0;
    cin>>n>>k;
    vector<int> nums;
    while (n--)
    {
        register int a=0;
        cin>>a;
        nums.push_back(a);
    }
    Solution solution;
    cout<<solution.findKthLeast(nums,k)<<endl;
    return 0;
}