C语言 查找数组中的前 n 个最大元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7272534/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding the first n largest elements in an array
提问by Poulami
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).
我有一个包含唯一元素的数组。我需要以尽可能低的复杂度找出数组中的前 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;
}
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!!
请，如果有人能想出一个更好的解决方案，它涉及的复杂性更低，我将不胜感激。而且我不打算改变原来的数组！！
回答by amit
Find the kth biggest element, using selection algorithm.
Next, iterate the array and find all elements which are larger/equal it.
使用选择算法找到第 k 个最大的元素。
接下来，迭代数组并找到所有大于/等于它的元素。
complexity:O(n) for selection and O(n) for iterating, so the total is also O(n)
复杂度：选择 O(n)，迭代 O(n)，所以总和也是 O(n)
回答by Alexandre C.
The usual trick to select the nlargest elements is to maintain a min-priority queue.
选择n 个最大元素的常用技巧是维护一个最小优先级队列。
- Unconditionnally insert into the queue the nfirst elements
- For each remaining element x, insert x if it is greater than the least element of the queue (O(log n) operation), and remove the least element (O(log n)).
- When done, the priority queue contains nelements, which are the nlargest elements of the original array.
- 无条件地将前n个元素插入队列
- 对于剩余的每个元素 x，如果 x 大于队列中的最小元素（O(log n) 操作），则插入 x，并删除最小元素（O(log n)）。
- 完成后，优先级队列包含n 个元素，它们是原始数组的n 个最大元素。
Total complexity: O(N log n) where N is the total number of elements in the array.
总复杂度：O(N log n)，其中 N 是数组中元素的总数。
I leave to you as an exercise the implementation details (first step is to learn about priority queues, and implement one).
我将实现细节留给您作为练习（第一步是了解优先级队列，并实现一个）。
回答by Man Vs Code
You can do this in O(n) if your elements are integers (or any integral type) within a range, i to k inclusive with k >= i. With this constraint, you can apply "bucket sort" to this.
如果您的元素是一个范围内的整数（或任何整数类型），您可以在 O(n) 中执行此操作，i 到 k 包括 k >= i。有了这个约束，你可以对此应用“桶排序”。
The idea is quite simple. Allocate k - i + 1 buckets. Now, iterate through your collection and increment the bucket for that integer. Then, at the end, you can "recreate" the sorted list by creating as many integers that were found (i.e. the bucket number).
这个想法很简单。分配 k - i + 1 个桶。现在，遍历您的集合并增加该整数的存储桶。然后，最后，您可以通过创建尽可能多的找到的整数（即桶号）来“重新创建”排序列表。
For example,
例如，
int collection[] = { 10, 4, 7, 1, 9, 0, 12 }; // maximum value to expect is 12, minimum is 0
int buckets[ 13 ] = { 0 };
for( int i = 0; i < 13; i++ )
{
int n = collection[ i ];
buckets[ n ]++;
}
// the first n largest elements (n = 4)
for( int j = 12; j >= 12 - 4; j-- )
{
int n = buckets[ j ];
while( n > 0 )
{
printf( "%d ", j );
n--;
}
}
printf( "\n" );
回答by Nam Nguyen
Use a modified version of Quick Sort. You do not need to actually sort the whole array. You only need to partition N elements larger than the pivot value. For more information, please read Introduction to Algorithms.
使用快速排序的修改版本。您实际上不需要对整个数组进行排序。您只需要对大于枢轴值的 N 个元素进行分区。有关更多信息，请阅读算法简介。
回答by harunrashid
You can use a Priority Queue using Heap (maxHeap) to solve this. Perform heap n times to get the first n largest elements. Each Heap operation takes O(log N) time, so N heap operations would result in O(N log N) time.
您可以使用使用 Heap (maxHeap) 的 Priority Queue 来解决此问题。执行堆 n 次以获取前 n 个最大元素。每个堆操作需要 O(log N) 时间，因此 N 堆操作将导致 O(N log N) 时间。
回答by Yashdeep Hinge
I don't believe on this but you could also create a heap out of it in O(n). And then just remove the root k number of times and heapify the heap for k largest numbers. In this way for each largest numbers it will cost you log(n).
我不相信这一点，但您也可以在 O(n) 中创建一个堆。然后只需删除根 k 次并将堆堆化为 k 个最大的数字。通过这种方式，对于每个最大的数字，您将花费 log(n)。
public class HeapSort1{
public static void main(String args[]){
int[] array={5,75,1,5,4,1,2,4,8,4,2,15,4,2,1,5,779,9,1};
int heapsize=array.length-1;
for(int i=heapsize/2;i>=0;i--){
maxHeapify(array,i,heapsize);
}
for(int i=heapsize;i>0;i--){
array[i]=array[0]+array[i];
array[0]=array[i]-array[0];
array[i]=array[i]-array[0];
maxHeapify(array,0,--heapsize);
}
printArray(array);
}
public static void maxHeapify(int[] array,int i,int heapsize){
int largest=i;
int left=2*i+1;
int right=2*i+2;
if(left<=heapsize && array[left]>array[i]){
largest=left;
}
if(right<=heapsize && array[right]>array[largest]){
largest=right;
}
if(largest!=i){
array[i]=array[largest]+array[i];
array[largest]=array[i]-array[largest];
array[i]=array[i]-array[largest];
maxHeapify(array,largest,heapsize);
}
}
public static void printArray(int[] array){
System.out.print("\n [");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
System.out.print("] \n");
}
public static int getMax(){
int max=array[0];
array[0]=array[heapsize];
maxHeapify(array,0,--heapsize);
}
}
回答by user1050619
I tried this as per @Alexandre C.
我按照@Alexandre C 尝试过这个。
This gets the top 10 items of a unbounded input. It breaks after it processed 20 items from the input.
这将获取无界输入的前 10 项。它在处理输入中的 20 个项目后中断。
import random
import time
top_10_items = []
cnt = 1
while True:
rand = random.randint(1,100)
print(rand)
time.sleep(1)
if len(top_10_items) !=10:
top_10_items.append(rand)
else:
m = min(top_10_items)
if rand > m:
top_10_items.append(rand)
top_10_items.remove(m)
print(top_10_items)
cnt+=1
if cnt==20:
break
回答by Rampedi Tshepo
//finding the bigest number in the array//
double big = x[0];
for(t=0;t<x[t];t++)
{
if(x[t]>big)
{
big=x[t];
}
}
printf("\nThe bigest number is %0.2lf \n",big);
