在一个数组中找到前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;
     }

请问是否有更简单的解决方案？如果有，我会非常感激。但是我不想改变原始数组！！

- Poulami

---

使用您喜欢的O(n log n)算法对数组进行排序，并选择前N个最大的元素。 - GWW

“前n个最大元素”是什么意思？是指最大的n个元素吗？还是前面的n个元素？ - blubb

http://en.wikipedia.org/wiki/Selection_algorithm - nibot

你的复杂度不是O(n^2)，而是O(n*k)，其中k是你想要的最大元素数量。只有当n=k时，它才是O(n^2)。因此，如果k足够小，那么你的算法并不那么糟糕。 - duedl0r

前往个人资料，选择其中一个问题，然后需要勾选最能回答你问题的答案。对于所有问题都要这样做。 - fazo

Answer 1

使用选择算法找到第k大的元素。
接下来，遍历数组并找到所有大于等于它的元素。

复杂度：选择算法为O(n)，遍历为O(n)，因此总复杂度也为O(n)。

- amit

---

但是，如果数组大小为n，并且您还需要找到最大的n个元素，则将运行n次，每次为O(n)，因此总共将是O(n^2)。最好对其进行排序。 - shinzou

不行。你在找到O(n)中的第n个最大元素后，将其命名为 x，然后在单独的一次迭代中找到所有满足 arr[i] >= x 的下标为 i 的元素。 这也可以在O(n)时间内完成，总计时间复杂度为 O(n + n) = O(n)。 - amit

@kuhaku，你可以先使用选择方法找到一个元素并知道它的值，然后只需迭代查找所有大于该元素的元素，无需再进行选择（请注意，输出结果未排序，您将得到未定义顺序的最大元素，但它们的内部顺序是未定义的）。 - amit

抱歉挖起这个问题，但是只用一次遍历数组并使用k个最大值的子集不会更快吗？对于每个新值，您将其与子集的最小值进行比较，如果它更大，则存储它并搜索新的子集最小值，否则继续前进。如果我没错的话，这将是k*k+(n-k)次迭代的最佳情况和k*n次迭代的最坏情况。 - Florent

@FlorentEcochard 我不确定我理解你的方法，但是 k*k + (n-k) = (k-1)*k + k + n-k = (k-1)*k + n，这是 O(k^2 + n)，比选择排序的 O(n) 更糟糕，特别是当 k->n 时，你会得到 O(n^2) 的时间复杂度，而选择排序只需要 O(n)。 - amit

Answer 2

通常选择前n个元素的技巧是维护一个最小优先队列。

• 无条件地将前n个元素插入队列中
• 对于每个剩余元素x，如果它大于队列中最小元素 (O(log n)操作)，则插入x并移除队列中最小元素(O(log n) 操作)。
• 完成后，优先队列包含n个元素，即原始数组的前n个最大元素。

总复杂度：O(N log n)，其中N是数组中元素的总数。

我留给你作为练习的实现细节（第一步是了解优先队列，并实现一个）。

- Alexandre C.

---

请注意，虽然这比@amit的基于QuickSelect的解决方案慢一些，但它是一种适用于无限输入流的在线算法。 - Yibo Yang

@YiboYang 是的，即使在有界的情况下，一切最终都取决于log n是否被认为很小。 - Alexandre C.

如果您需要排序后的结果，请使用此解决方案。否则请使用Amit的解决方案。 - Barry Fruitman

@BarryFruitman：如果您只允许一次通过数据，或者数据不适合内存，请使用我的版本。 - Alexandre C.

Answer 3

如果您的元素是整数（或任何整数类型）且在范围i到k内，且k >= i，则可以以O(n)的时间复杂度完成此操作。在这种限制下，您可以对其应用“桶排序”。

思路非常简单。分配k-i+1个桶。现在，遍历您的集合并增加该整数的桶。然后，在结束时，您可以通过创建与找到的整数数量相同的整数（即桶编号）来“重新创建”已排序的列表。

例如，

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" ); 

- Man Vs Code

---

请回答这个问题：如何找到数组中最大的n个元素并打印出来？ - S.G

Answer 4

使用修改版的快速排序。您不需要实际对整个数组进行排序。您只需要将大于枢轴值的N个元素进行分区。更多信息，请阅读《算法导论》。

- Nam Nguyen

---

我想在不使用任何排序算法的情况下完成它！！ - Poulami

这是一道家庭作业题吗？这个要求看起来非常具体。 - Vanessa MacDougal

@Poulami：你不觉得这是值得在问题中提及的细节吗？ - Praetorian

除了@Poulami的要求之外，我不认为这实际上会起作用-快速排序中选择枢轴值通常是随机的。要做出非随机的猜测，您需要事先了解有关元素顺序或大小的某些信息，在这种情况下您没有这些信息。 - Apoorv Khatreja

Answer 5

你可以使用使用堆（最大堆）来解决优先队列问题。执行n次堆操作以获取前n个最大的元素。每个堆操作需要O(log N)的时间，因此N个堆操作将导致O(N log N)的时间复杂度。

- harun_a

---

这里的复杂性分析有问题（具体来说：错误地使用了相同的变量N来表示输入和输出的大小）。 - Ben Voigt

Answer 6

我按照 @Alexandre C. 的建议尝试了这个。

这获取无限输入的前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

- user1050619

Answer 7

我不太相信，但你也可以在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);
    }

 }                                                                                                                                                             

- Yashdeep Hinge

Answer 8

    //First we sort the array in descending order and after the array 
//is sorted, we print the number of largest elements we want

  import java.util.Scanner;
class bubble_sort{
    
    static void buuble_sort(int[] array,int n){

        int temp=0;
//I have sorted this array using bubble sorting technique, in case you don't know, you must know, it's effective, easy and fast.

        for (int i=0; i<n;++i){
            for (int j=0;j<n-1;j++){
                if (array[j]<array[j+1]){
                     temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
    }
//this method print the number of 'n' largest we want.
    static void print_sort(int array[],int num){
        for (int i=0;i<num;++i){
            System.out.print(array[i]+" ");
        }
    }

public static void main(String[] args)
{
         Scanner obj=new Scanner(System.in);   
    int[] array={12, 34, 56, 32, 45, 22,3, 18};
    int n=array.length;
     System.out.println("the elements of the array are as follows:-");
     for (int i=0; i<array.length;++i){
        System.out.print(array[i]+" ");
     }
    buuble_sort(array,n);
    System.out.print("\nEnter the number of largest elements you want from the above array : ");
//give the integer input as 'n' number of largest elements.
    int num=obj.nextInt();
    print_sort(array,num);
        

}
}

- alok singh

---

你为什么用未注释和未格式化的Java代码回答一个已经被接受超过10年的C语言问题？ - undefined

Answer 9

//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);

- Rampedi Tshepo