Jun 14

nth element: 你需要什么? 不指定

felix021 @ 2009-6-14 21:23 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(8586) | Via 本站原创 | |
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速度。。。

所以你应该尽可能少地扫描。

于是这时候最小堆就是最优解决方案:只扫描一遍,就可以得出结果。

------

代码如下:

//最小堆
#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;
    }
}


转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: http://www.felix021.com/blog/feed.php
qq
2009-10-25 09:51
pig谢啦啊
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]