思路
找第 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; }