思路：固定一个数，把这个数放到合法的位置，然后左边的数都是比它小，右边的数都是比它大
固定权值选的是第一个数，或者一个随机数
因为固定的是左端点，所以一开始需要在右端点开始，找一个小于权值的数，从左端点开始，找一个大于权值的数
那么交换他们即可、最后的话，One == two那个位置就是权值应该去到的位置，这个时候把原问题划分为更小的子问题
就是[be, one - 1]和[one + 1, en]这两个子问题。
下面的是有bug的，当rand去到en的时候，就会wa （修复了）
比如数据是，4、5、1、2就很容易wa
用随机做了一个TLE了，还没wa就TLE了
http://codeforces.com/contest/732/problem/D
ID = be也是TLE，不明白STL的sort是怎么来的
int myRand(int be, int en) { return be + (rand() % (en - be + 1)); } void quickSort(int a[], int be, int en) { if (be >= en) return ; int id = myRand(be, en); // 这样不行，需要id = be int one = be, two = en; while (one != two) { while (two > one && a[two] >= a[id]) --two; // 找第一个比id小的, 必须先找小的 while (one < two && a[one] <= a[id]) ++one; // 找第一个比id大的, 因为基准数是be if (one < two) swap(a[one], a[two]); //固定id = be，需要从右到左是因为，如果是从左到右，例子1、2、3、4、5 //找到第一个比1大的，是2，然后找不到第一个比1小，在2中相遇 //然后swap(a[1], a[2]) GG } swap(a[id], a[one]); quickSort(a, be, one - 1); quickSort(a, one + 1, en); }
修复：
随机一个id，然后和第一那个数交换，就可以了。和id = be一样了
int myRand(int be, int en) { return be + (rand() % (en - be + 1)); } void quickSort(int a[], int be, int en) { if (be >= en) return ; int id = myRand(be, en); // swap(a[be], a[id]); id = be; int one = be, two = en; while (one != two) { while (two > one && a[two] >= a[id]) --two; // 找第一个比id小的, 必须先找小的 while (one < two && a[one] <= a[id]) ++one; // 找第一个比id大的, 因为基准数是be if (one < two) swap(a[one], a[two]); //固定id = be，需要从右到左是因为，如果是从左到右，例子1、2、3、4、5 //找到第一个比1大的，是2，然后找不到第一个比1小，在2中相遇 //然后swap(a[1], a[2]) GG } swap(a[id], a[one]); quickSort(a, be, one - 1); quickSort(a, one + 1, en); }
随机生成区间里的一个数字思路：
区间大小是len，那么就生成一个0---len-1的数，加上起始点，就是落在[be, en]的数
代码在上面。
O(n)找第k小的数
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 1e5 + 20; int myRand(int be, int en) { return be + (rand() % (en - be + 1)); } int findKthMin(int a[], int be, int en, int k) { if (be == en) return a[be]; swap(a[be], a[myRand(be, en)]); int one = be, two = en, id = be; while (one != two) { while (two > one && a[two] >= a[id]) --two; // 找第一个比id小的, 必须先找小的 while (one < two && a[one] <= a[id]) ++one; // 找第一个比id大的, 因为基准数是be if (one < two) swap(a[one], a[two]); //需要从右到左是因为，如果是从左到右，例子1、2、3、4、5 //找到第一个比1大的，是2，然后找不到第一个比1小，在2中相遇 //然后swap(a[1], a[2]) GG } swap(a[id], a[one]); int hasKey = one - be + 1; // 有多少个元素 if (hasKey >= k) return findKthMin(a, be, one, k); else return findKthMin(a, one + 1, en, k - hasKey); } int a[maxn]; void work() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } printf("%d ", findKthMin(a, 1, n, 4)); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
找前k大的数，首先找到第n - k + 1小的数，那么这些数的右边，都是比它大的，这个时候就是前k大了，直接排序一下就好
#include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 1000000 + 20; int myRand(int be, int en) { return be + (rand() % (en - be + 1)); } int findKthMin(int a[], int be, int en, int k) { if (be == en) return be; swap(a[be], a[myRand(be, en)]); int one = be, two = en, id = be; while (one != two) { while (two > one && a[two] >= a[id]) --two; // 找第一个比id小的, 必须先找小的 while (one < two && a[one] <= a[id]) ++one; // 找第一个比id大的, 因为基准数是be if (one < two) swap(a[one], a[two]); //需要从右到左是因为，如果是从左到右，例子1、2、3、4、5 //找到第一个比1大的，是2，然后找不到第一个比1小，在2中相遇 //然后swap(a[1], a[2]) GG } swap(a[id], a[one]); int hasKey = one - be + 1; // 有多少个元素 if (hasKey >= k) return findKthMin(a, be, one, k); else return findKthMin(a, one + 1, en, k - hasKey); } int a[maxn]; void work() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } int id = findKthMin(a, 1, n, n - k + 1); sort(a + id, a + 1 + n); for (int i = n; i >= id; --i) { printf("%d ", a[i]); } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }