Jun
14
nth element: 你需要什么?
nth element, 也就是要找出一个数列中排名第n的那个数。
很直观地,把所有的数排序以后,就可以得出这nth element了。
快排测试:4.5s,1千万个int。
仔细想一下,这似乎有点浪费:其实只要找出最大的n个就行了。
如果n比较小,我们可以直接用选择排序。
这个程序太简单了,懒得测试。
然后再仔细想一下,发现还是有点浪费,其实前n个数不需要排序。
于是可以用最小堆来实现。
测试结果:3.02s,1千万个int,n = 500。
然后你可能会发现,STL里面有个函数,叫做nth_element,就是用来做这个的
测试一下:3.4s,1千万个int, n = 500。
如果想要深入了解,那么实际上这个nth_element使用的算法是快速划分。
它其实就是不完全的快速排序,只要递归地排序需要排序的部分就可以了。
自写代码测试:3.4s,1千万个int, n = 500。
------
从上面可以看出,在k=500(N = 10,000,000)时,最小堆是最快的,其次是快速划分,快排当然最慢。
最小堆的时间复杂度是 O( N * log(k) )
快速划分虽然平均时间复杂度是O(C*N)(但是C比较大),但是最坏时间复杂度是O(N^2)(所以随机化很重要!可以避免RPWT!)
快排就不用说了,撑死 O(N * log(N) ),最坏时间复杂度也可能是O(N^2)。
似乎最小堆是最快的,快速划分慢些,但是它们各有自己的适用范围:
当 k 接近 N / 2时,最小堆的时间复杂度其实就相当于一个堆排,事实上还不如快排。
所以最小堆的适用范围是k << N时的情况,或者当k 很接近N, 可以转化成 N-k << N的情况。
而快速划分的算法本身决定了其复杂度和 k 的大小无关,所以当 k 接近 N/2 时,快速划分显然更优。
可是还有另一种情况,也是大公司面试的时候很可能会问到的题目:
给你200亿个整数,找出TOP500000。
第一次遇到这个问题,估计大多数人直接口突白沫了吧。
200亿,对一般PC而言,内存显然存不下,需要保存在辅存中,而辅存的IO速度。。。
所以你应该尽可能少地扫描。
于是这时候最小堆就是最优解决方案:只扫描一遍,就可以得出结果。
------
代码如下:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
很直观地,把所有的数排序以后,就可以得出这nth element了。
快排测试:4.5s,1千万个int。
仔细想一下,这似乎有点浪费:其实只要找出最大的n个就行了。
如果n比较小,我们可以直接用选择排序。
这个程序太简单了,懒得测试。
然后再仔细想一下,发现还是有点浪费,其实前n个数不需要排序。
于是可以用最小堆来实现。
测试结果:3.02s,1千万个int,n = 500。
然后你可能会发现,STL里面有个函数,叫做nth_element,就是用来做这个的
测试一下:3.4s,1千万个int, n = 500。
如果想要深入了解,那么实际上这个nth_element使用的算法是快速划分。
它其实就是不完全的快速排序,只要递归地排序需要排序的部分就可以了。
自写代码测试:3.4s,1千万个int, n = 500。
------
从上面可以看出,在k=500(N = 10,000,000)时,最小堆是最快的,其次是快速划分,快排当然最慢。
最小堆的时间复杂度是 O( N * log(k) )
快速划分虽然平均时间复杂度是O(C*N)(但是C比较大),但是最坏时间复杂度是O(N^2)(所以随机化很重要!可以避免RPWT!)
快排就不用说了,撑死 O(N * log(N) ),最坏时间复杂度也可能是O(N^2)。
似乎最小堆是最快的,快速划分慢些,但是它们各有自己的适用范围:
当 k 接近 N / 2时,最小堆的时间复杂度其实就相当于一个堆排,事实上还不如快排。
所以最小堆的适用范围是k << N时的情况,或者当k 很接近N, 可以转化成 N-k << N的情况。
而快速划分的算法本身决定了其复杂度和 k 的大小无关,所以当 k 接近 N/2 时,快速划分显然更优。
可是还有另一种情况,也是大公司面试的时候很可能会问到的题目:
给你200亿个整数,找出TOP500000。
第一次遇到这个问题,估计大多数人直接口突白沫了吧。
200亿,对一般PC而言,内存显然存不下,需要保存在辅存中,而辅存的IO速度。。。
所以你应该尽可能少地扫描。
于是这时候最小堆就是最优解决方案:只扫描一遍,就可以得出结果。
------
代码如下:
//最小堆
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
struct heap{
int d[501];
int n;
void sift_down(int i){
while(2 * i <= n){
i *= 2;
if(i + 1 <= n && d[i] < d[i+1]) i++;
if(d[i/2] < d[i]){
swap(d[i/2], d[i]);
}else{
break;
}
}
}
void make_heap(){
for(int i = n / 2; i >= 1; --i){
sift_down(i);
}
}
void dump(){
for(int i = 1; i <= n; ++i){
printf("%d ", d[i]);
}
printf("\n");
}
};
int main(){
int t;
heap h1;
srand(time(0));
while(scanf("%d", &t) == 1){
h1.d[h1.n] = t;
if(h1.n == 500) break;
h1.n++;
}
h1.make_heap();
while(scanf("%d", &t) == 1){
if(t < h1.d[1]){
h1.d[1] = t;
h1.sift_down(1);
}
}
printf("%d\n", h1.d[1]);
h1.dump();
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;
struct heap{
int d[501];
int n;
void sift_down(int i){
while(2 * i <= n){
i *= 2;
if(i + 1 <= n && d[i] < d[i+1]) i++;
if(d[i/2] < d[i]){
swap(d[i/2], d[i]);
}else{
break;
}
}
}
void make_heap(){
for(int i = n / 2; i >= 1; --i){
sift_down(i);
}
}
void dump(){
for(int i = 1; i <= n; ++i){
printf("%d ", d[i]);
}
printf("\n");
}
};
int main(){
int t;
heap h1;
srand(time(0));
while(scanf("%d", &t) == 1){
h1.d[h1.n] = t;
if(h1.n == 500) break;
h1.n++;
}
h1.make_heap();
while(scanf("%d", &t) == 1){
if(t < h1.d[1]){
h1.d[1] = t;
h1.sift_down(1);
}
}
printf("%d\n", h1.d[1]);
h1.dump();
return 0;
}
//快速划分,Range is [s, e)
int quick_select(int d[], int s, int e, int n){
//错误的情况
if(n < 0 || n > e - s) return -1;
if(s + 1 < e){
int i = s, j = e - 1, t;
//随机化
t = rand() % (e - s) + s;
swap(d[t], d[s]);
t = d[s];
//划分
while (i != j){
while(d[j] >= t && i != j) j--;
if(i != j) d[i] = d[j], i++;
while(d[i] < t && i != j) i++;
if(i != j) d[j] = d[i], j--;
}
d[i] = t;
//找出段[i, j), 期间的所有数字都相同
for(j = i + 1; j < e && d[j] == d[i]; ++j);
// [s, i)小于d[i], [i, j)等于d[i], [j, e)大于d[i]
int t1 = i - s, t2 = j - i;
if(t1 >= n){
return quick_select(d, s, i, n);
}
n -= t1;
if(t2 >= n){
return (i + n - 1);
}
return quick_select(d, j, e, n - t2);
}else if(s + 1 == e){
return s;
}else{
return -1;
}
}
int quick_select(int d[], int s, int e, int n){
//错误的情况
if(n < 0 || n > e - s) return -1;
if(s + 1 < e){
int i = s, j = e - 1, t;
//随机化
t = rand() % (e - s) + s;
swap(d[t], d[s]);
t = d[s];
//划分
while (i != j){
while(d[j] >= t && i != j) j--;
if(i != j) d[i] = d[j], i++;
while(d[i] < t && i != j) i++;
if(i != j) d[j] = d[i], j--;
}
d[i] = t;
//找出段[i, j), 期间的所有数字都相同
for(j = i + 1; j < e && d[j] == d[i]; ++j);
// [s, i)小于d[i], [i, j)等于d[i], [j, e)大于d[i]
int t1 = i - s, t2 = j - i;
if(t1 >= n){
return quick_select(d, s, i, n);
}
n -= t1;
if(t2 >= n){
return (i + n - 1);
}
return quick_select(d, j, e, n - t2);
}else if(s + 1 == e){
return s;
}else{
return -1;
}
}
欢迎扫码关注:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
qq
2009-10-25 09:51
谢啦啊
分页: 1/1 1