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

• Z时代
• 2024-01-10
• 分类：问答

我有一个包含唯一元素的数组。我需要以最小的复杂度找出数组中的前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;
     }

请，如果有人能提出一个更好的解决方案，而涉及的复杂性更低，我将非常感激。而且我不打算更改原始数组！

回答：

使用选择算法找出第k个最大元素。

接下来，迭代数组并找到所有大于/等于数组的元素。

用于选择的O（n）和用于迭代的O（n），因此总数也为O（n）

以上是 查找数组中的前n个最大元素 的全部内容， 来源链接： utcz.com/qa/399195.html