查找数组中的前n个最大元素

Question

我有一个包含唯一元素的数组.我需要以尽可能最小的复杂性找出数组中的前n个最大元素.到目前为止,我能想到的解决方案具有O(n ^ 2)的复杂性.

    int A[]={1,2,3,8,7,5,3,4,6};
    int max=0;
    int i,j;
    int B[4]={0,0,0,0,};//where n=4;
     for(i=0;i<A.length();i++)
       {
         if(A[i]>max)
          max=A[i];
       }
     B[0]=max;
     for(i=1;i<n;i++){
       max=0;
       for(j=0;j<A.length();j++){
         if(A[j]>max&&A[j]<B[i-1])
            max=A[j];
       }
        B[i]=max;
     }

如果有人能提出一个更复杂的解决方案,我将非常感激.而且我不打算改变原来的阵列!

Answer 1

使用选择算法找到第k个最大元素.
接下来,迭代数组并找到所有大于/等于它的元素.

复杂度: O(n)用于选择,O(n)用于迭代,因此总数也是O(n)

Answer 2

选择n个最大元素的常用技巧是维护最小优先级队列.

• 无条件地将n个第一个元素插入队列
• 对于每个剩余元素x,如果它大于队列的最小元素(O(log n)操作),则插入x,并删除最小元素(O(log n)).
• 完成后,优先级队列包含n个元素,这些元素是原始数组的n个最大元素.

总复杂度:O(N log n)其中N是数组中元素的总数.

我将练习详细信息留给您(第一步是了解优先级队列,并实现一个).