Поиск первых n наибольших элементов в массиве

У меня есть массив, содержащий уникальные элементы. Мне нужно узнать первые 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;
     }

Пожалуйста, если кто-нибудь может придумать лучшее решение, которое потребует меньшей сложности, я буду очень благодарен. И я не собираюсь менять исходный массив!

Ответ 1

Найдите k-й самый большой элемент, используя алгоритм выбора.
Затем итерации массива и найти все элементы, которые больше/равны.

сложность: O (n) для выбора и O (n) для итерации, поэтому общее число также равно O (n)

Ответ 2

Обычный трюк для выбора n наибольших элементов - это поддерживать очередь с минимальным приоритетом.

Необычно вставить в очередь n первых элементов
Для каждого оставшегося элемента x вставьте x, если он больше, чем наименьший элемент очереди (операция O (log n)), и удалите наименьший элемент (O (log n)).
Когда это делается, очередь приоритетов содержит n элементов, которые являются n наибольшими элементами исходного массива.

Общая сложность: O (N log n), где N - общее количество элементов в массиве.

Я оставляю вам как упражнение детали реализации (первый шаг - узнать о очередях приоритетов и реализовать один).

Ответ 3

Вы можете сделать это в O (n), если ваши элементы являются целыми (или любым целым типом) в пределах диапазона, от я до k включительно с k >= i. С этим ограничением вы можете применить к этому свойству "ведро".

Идея довольно проста. Выделите k - я + 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" );

Ответ 4

Используйте модифицированную версию Quick Sort. Вам не нужно сортировать весь массив. Вам нужно только разделять N элементов больше, чем значение поворота. Для получения дополнительной информации ознакомьтесь с "Введение в алгоритмы".

Ответ 5

Вы можете использовать очередь приоритетов с помощью кучи (maxHeap), чтобы решить эту проблему. Выполните кучу n раз, чтобы получить первые n наибольших элементов. Каждая операция кучи принимает время O (log N), поэтому N операций кучи приведет к O (N log N) времени.

Ответ 6

Я не верю в это, но вы также можете создать кучу из него в O (n). А затем просто удалите корень k количество раз и heapify кучу для 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);
    }

 }

Ответ 7

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