题目描述
blablabla
样例
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
vector<int> display(vector<int> &arr, int left, int right) {
int tmp = arr[right];
int start = left - 1;
int end = right + 1;
int now = right;
while(start < now) {
if(arr[now] == tmp) {
now--;
}
else if(arr[now] < tmp) {
start++;
swap(arr[now], arr[start]);
}
else {
end--;
swap(arr[now], arr[end]);
now--;
}
}
return vector<int>{start, end};
}
void quicksort(vector<int> &arr, int left, int right, int k) {
if(left >= right) return;
if(k<left || k>right) return;
int idx = rand()%(right-left+1) + left;
swap(arr[idx], arr[right]);
vector<int> lr = display(arr, left, right);
if(k<=lr[0]) quicksort(arr, left, lr[0], k);
if(k>=lr[1]) quicksort(arr, lr[1], right, k);
}
int main() {
int n,k,tmp;
vector<int> arr;
cin >> n >> k;
while(cin >> tmp) {
arr.push_back(tmp);
}
srand(time(0));
quicksort(arr, 0, arr.size()-1, k-1);
cout << arr[k-1] << endl;
for(int i=0; i<arr.size(); i++) {
cout << arr[i] << ' ';
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla