三路快速选择 TLE

TommyBay @ 2021-11-17 19:09:41

//三路快选
//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;
}

by 红黑树 @ 2021-11-17 19:14:01

@TommyBay

//三路快选 O2
//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  n=0, k=0;
    scanf("%d%d", &n, &k);
    vector<int> nums;
    while (n--)
    {
        int a=0;
        scanf("%d", &a);

        nums.push_back(a);
    }
    Solution solution;
    cout<<solution.findKthLeast(nums,k)<<endl;

    // cout<<"Hello VS Code"<<endl;
    //cout<<"<Done.";
    return 0;
}

by 红黑树 @ 2021-11-17 19:14:22

@TommyBay scanf()

by 红黑树 @ 2021-11-17 19:15:47

不开 O2 也能过

by NetherDevil @ 2021-11-17 19:19:41

@TommyBay 建议在读入量大的时候使用

ios::sync_with_stdio(false);

解除同步加速 cin 的效率，还可以

cin.tie(NULL);

进一步加速；或者直接使用

scanf()

垃圾 Markdown 检测，又双叒叕出 Bug（（

by TommyBay @ 2021-11-17 19:23:45

@红黑树 感谢! 刚才我也自己改成了这个, cstdio还是我大爷(

by TommyBay @ 2021-11-17 19:24:07

@LocalSystem 感谢指教! 学习了!