查找数组中的前 n 个最大元素 [英] Finding the first n largest elements in an array
问题描述
我有一个包含唯一元素的数组.我需要以尽可能低的复杂度找出数组中的前 n 个最大元素.到目前为止我能想到的解决方案的复杂度为 O(n^2).
I have got an array containing unique elements. I need to find out the first n largest elements in the array in the least complexity possible. The solution that I could think of so far has a complexity of 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;
}
请,如果有人能想出一个更简单的解决方案,我将不胜感激.而且我不打算改变原来的数组!!
Please, if anyone can come up with a better solution which involves less complexity, I will be highly grateful. And I don't intend to change the original array!!
推荐答案
找到第 k 个最大的元素,使用 selection算法.
接下来,迭代数组并找到所有大于/等于它的元素.
Find the kth biggest element, using selection algorithm.
Next, iterate the array and find all elements which are larger/equal it.
复杂度: O(n) 用于选择,O(n) 用于迭代,所以总和也是 O(n)
complexity: O(n) for selection and O(n) for iterating, so the total is also O(n)
这篇关于查找数组中的前 n 个最大元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!