题目链接 AcWing 785
已经随机化处理 但还是超时 leetcode 是可以通过的
错误的代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, a[N];
int part(int L, int R) {
int p = rand() % (R - L + 1) + L;// p = (L + R) / 2 也超时
swap(a[p], a[R]);
int i = L;
for (int j = L; j < R; ++j) {
if (a[j] < a[R]) swap(a[i++], a[j]);
}
swap(a[i], a[R]);
return i;
}
void qs(int L, int R) {
if (L >= R) return;
int p = part(L, R);
qs(L, p - 1);
qs(p + 1, R);
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
qs(0, n - 1);
for (int i = 0; i < n; ++i) cout << a[i] << " ";
return 0;
}
TLE
