Нахождение первых n самых больших элементов в массиве - PullRequest
Новая
       7

Нахождение первых n самых больших элементов в массиве

14 голосов
/ 01 сентября 2011

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

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

Ответы [ 8 ]

30 голосов
/ 01 сентября 2011

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

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

11 голосов
/ 01 сентября 2011

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

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

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

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

2 голосов
/ 01 сентября 2011

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

Идея довольно проста. Выделите 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" );
1 голос
/ 11 ноября 2013

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

1 голос
/ 01 сентября 2011

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

0 голосов
/ 14 августа 2018

Я пробовал это согласно @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
0 голосов
/ 19 января 2017

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

 }
0 голосов
/ 15 марта 2013 
//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);
...