文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
恩，这个学期开算法课，跟着进度写写代码就好。这周讲分治，说到了求N个数中第K小(大)数的问题，写写看。
分治算法的复杂度是O(n)，用到了快速排序的思路：先选取一个参考数进行一次快排，拿升序来说的话，快排之后左边所有数<参考数，右边所有数>参考数，然后根据左右部分各自包含元素的个数，计算要求的元素在哪个区间内(要求的元素或是左区间中的第k小数，或是右区间中第[k-j]小数，j为左区间的长度)，然后递归求解。
本来pku 2104和pku 2761都是求第K小数的题，无奈用这个算法TLE，只能用后面的划分树或是其他复杂度更低的算法来做，以后再说吧。我这里只贴用这个算法做的，虽然交上去会TLE…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> using namespace std; int partition(int[], int, int); int Select(int[], int, int, int); int main() { int n, m; int l, r, k; int v[100002]; int d[100002]; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> v[i]; while (m--) { cin >> l >> r >> k; for (int j = l; j <= r; j++) d[j] = v[j]; cout << Select(d, l, r, k) << endl; } return 0; } //一次快速排序 int partition(int s[], int l, int r) { if (l < r) { int i = l; int j = r; int x = s[i]; while (i < j) { while (i < j && s[j] > x) j--; if (i < j) s[i++] = s[j]; while (i < j && s[i] < x) i++; if (i < j) s[j--] = s[i]; } s[i] = x; return i; } return -1; } //分治找K-th Number int Select(int s[], int l, int r, int k) { if (l > r) return -1; if (l == r) return s[l]; //得到中间数的下标 int i = partition(s, l, r); //j为左区间长度 int j = i - l + 1; //位置大就在左区间找，否则就在右区间找 if (j == k) return s[i]; else if (j > k) return Select(s, l, i, k); else return Select(s, i+1, r, k-j); } |
转载请注明：Slyar Home » 分治算法求N个数中第K小(大)的数
