我有包含唯一元素的数组。我需要找出数组中的第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个最大的元素,使用选择算法 。结果接下来,遍历数组,发现这是更大的所有元素/平等的。
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个最大元素
发布评论