查找第 K 小数

思路

找第 K 小数，第一反应是全体排序，快排、归并 blabla，时间复杂度 O(nlogn)，或者直接用 set，去重也省了，但是这样做有点无聊

#include<iostream>
#include<set>

using namespace std;

int main(){
    int n, k;
    while(cin >> n){
        set<int> nums;
        int num;
        for(int i = 0; i < n; i ++){
            cin >> num; nums.insert(num);
        }
        cin >> k;
        for(auto it = nums.begin(); it != nums.end(); it ++){
            k --;
            if(k == 0){
                cout << *it << endl; break;
            }
        }
    }
    return 0;
}

如果不考虑去重的话，我们可以用快排的思路去取第 K 小的数，平均时间复杂度为 O(n)，但是因为要去重，这里借助一下 unordered_set 去一下重

#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int partition(vector<int>& nums, int low, int high){
    int pivot = nums[low];
    while(low < high){
        while(low < high && nums[high] >= pivot) high --;
        nums[low] = nums[high];
        while(low < high && nums[low] <= pivot) low ++;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}

int quickSelect(vector<int>& nums, int low, int high, int k){
    int p = partition(nums, low, high);
    if(p == k) return nums[p];
    else if(p > k) return quickSelect(nums, low, p - 1, k);
    else return quickSelect(nums, p + 1, high, k);
}
int main(){
    int n, k;
    while(cin >> n){
        unordered_set<int> temp;
        int num;
        for(int i = 0; i < n; i ++){
            cin >> num;
            temp.insert(num);
        }
        vector<int> nums(temp.begin(), temp.end());
        cin >> k;
        cout << quickSelect(nums, 0, nums.size() - 1, k - 1) << endl;
    }
    return 0;
}