3

我想设计一个函数来查找具有时间复杂度的 N 个无序元素集合中的 k 个最大元素：Θ(N+klogN)在线判断。

这是一个示例：

输入

LN 1 : N K

LN 2 : N numbers

输出

LN 1 : K biggest number

LN 2 : Final heap

样本输入

10 4
17 19 26 37 30 11 5 29 32 1

样本输出

29
26 19 11 17 1 5

这是我的代码：

#include <iostream>

using namespace std;

int main(){

    int i,j,rc,temp,temp1,length,K;
    cin>>length>>K;
    int *heap = new int[length];

    for(i=0;i<length;i++) cin>>heap[i];
    for(i=length/2-1;i>=0;i--){                  //build a max heap first with Θ(N)
        while(!((i>=length/2)&&(i<length))){
            j = 2*i+1;
            rc = 2*i+2;
            if((rc<length)&&(heap[j]<heap[rc])) j=rc;
            if(heap[i]>heap[j]) break;
            temp = heap[i];
            heap[i]=heap[j];
            heap[j]=temp;
            i=j;
        }
    }
    int k,n=length;
    for(k=0;k<K;k++){                         //shiftdown k times to find k biggest 
        temp1=heap[--n];                      //numbers with Θ(klogN)
        heap[n] = heap[0];
        heap[0] = temp1;
        if(n!=0) {
            i=0;
                while(!((i>=n/2)&&(i<n))){
                     j = 2*i+1;
                    rc = 2*i+2;
                    if((rc<n)&&(heap[j]<heap[rc])) j=rc;
                    if(heap[i]>heap[j]) break;
                    temp = heap[i];
                    heap[i]=heap[j];
                    heap[j]=temp;
                    i=j;
                }
            }
        }


    cout<<heap[length-K]<<endl;
    for(i=0;i<length-K;i++)
        cout<<heap[i]<<" ";
    return 0;
}

没关系，但是其中一个数据是 Time Limit Exceed ，我对如何解决这个问题感到很困惑。

4

3 回答 3

0

您的筛选操作似乎不正确。那里不应该有两个嵌套循环。您应该从根开始并继续与它的一个孩子交换它，直到它比两者都大。外部循环for(i=n/2-1;i>=0;i--)不应该存在（它会导致每次筛选O(n)） - 我认为您应该设置i为 0 以从根开始。

编辑：您的 heapify 操作也太慢了：您i对外部和内部循环使用相同的循环变量，因此它会交替变大和变小。内循环应该从外循环的 开始i，但不应该影响i外循环下一次迭代中的值。我建议将筛选操作放在它自己的功能中。这既可以解决这个问题，又可以避免筛选编码两次。

于 2012-11-04T09:53:17.853 回答
0

我猜是一些 onlinejudge.org 比赛。为什么不分享问题链接？

然后我们可能会判断您是否真的需要堆排序，或者您是否会更好地使用诸如 QuickSelect 之类的东西和一个好的启发式方法。

我的猜测是，简单的堆排序不足以满足他们的一个测试用例。

您可能还需要添加优化，例如在开头和结尾检查预排序的数据或反向排序的数据（和数据部分）。避免为这些部分构建堆，但保持原样。

尝试在一个巨大的反向排序列表上运行 heapsort ，k 很大，IIRC 是最坏的情况（对于最大堆，任何最小堆都应该是最坏的情况，反之亦然）。

典型的在线法官测试用例通常是围绕这些已知的最坏情况精心设计的。然后设置时间限制，即使使用非常好的优化O(n + k log n)解决方案，与真正的解决方案相比，您也会失败O(n)。他们只需要使 k 足够大。他们来自比赛，他们想通过给他们真正的平均输入文件来挑战人们！

PS 你的堆构建好像也太复杂了。问题是你又增加i了。你不应该这样做。通过在 while 循环中增加 i，您会导致自下而上的堆构造再次“重新启动”多次。所以你的堆构建可能不再是O(n).

于 2012-11-04T09:53:57.977 回答
0

您可能想检查三个不同序列会发生什么：

    1. 4 2 1 2 3 4
    1. 4 2 4 3 2 1
    1. 4 2 1 1 1 1
 int NN=0;
 for(i=length/2-1;i>=0;i--){                  //build a max heap first with Θ(N)
cout << "i=" << i << "\n";
    while(!((i>=length/2)&&(i<length))){
        j = 2*i+1;
        rc = 2*i+2;
        cout << NN++ << " " << j << " " << rc << " " << i << "\n";
        if((rc<length)&&(heap[j]<heap[rc])) j=rc;
        if(heap[i]>heap[j]) break;
        temp = heap[i];
        heap[i]=heap[j];
        heap[j]=temp;
        i=j;
    }
}

在最后一种情况下，循环将稳定到 j=3；rc=4; 我=1；

也许内部循环应该使用单独的变量而不是“i”。

于 2012-11-04T11:58:29.000 回答