Три величайших значения в массиве

Question

Чтобы найти три самых больших элемента в массиве (длина 100), представляет собой комбинацию цикла for и оператора if (s) наиболее эффективным способом или существует более эффективный метод?

Answer 1

Для массива длиной 100 и макс-3 элементов вы можете сначала отсортировать массив, а затем взять верхние три элемента - разница в производительности незначительна.

Для массива большего размера, для цикла с if, если сравнивать 3 элемента с текущим, отлично.

Если вам нужно найти верхние N элементов массива M-размера, то я думаю, что сортировка будет наиболее эффективной.

Answer 2

Предполагая, что массив не отсортирован, вы должны пройти через каждый элемент с цикл (или что-то эквивалент.)

Там на самом деле не более эффективный способ, но для итерации для каждого элемента.

Answer 3

Вам нужно пройти только один раз, но да, вам придется пройти его (при условии, что он не отсортирован).

Answer 4

Я думаю, вы могли бы сделать это с помощью одного цикла через массив, и я не думаю, что вы могли бы сделать это быстрее. Что-то вроде:

int max1 = Integer.MIN_VALUE; 
int max2 = Integer.MIN_VALUE; 
int max3 = Integer.MIN_VALUE; //assuming integer elements in the array 

for (int i = 0; i < theArray.length; i++) 
{ 
    if (theArray[i] > max1) 
    { 
     max3 = max2; max2 = max1; max1 = theArray[i]; 
    } 
    else if (theArray[i] > max2) 
    { 
     max3 = max2; max2 = theArray[i]; 
    } 
    else if (theArray[i] > max3) 
    { 
     max3 = theArray[i]; 
    } 
} 

Если вы хотите топ N элементов в массиве, вы, вероятно, просто хочу, чтобы отсортировать его.

Answer 5

Лучший и самый эффективный способ (по моему мнению) будет сортировать массив сначала (желательно с Merge Sort), затем получить верхние 3 значения.

Answer 6

Поскольку это java, вы всегда можете использовать SortedSet (например, TreeSet), который выполняет сортировку, когда элементы вставлены с минимальными затратами (log (n)), и когда вы закончите вставку, вы может использовать descendingIterator() для извлечения трех величайших элементов.

Answer 7

Ваш вопрос не очень ясен для меня.

Наиболее эффективным способом было бы поддерживать максимальную кучу размера 3 и вставлять элементы массива в максимальную кучу по одному.

В конце элементы 3 в вашей максимальной куче - это самые большие элементы в исходном массиве 3.

В целом проблема поиска макс. M элементов в массиве размером N лучше всего решить путем поддержания максимальной кучи размера M.

Answer 8

Несколько человек публикуют сообщение о том, что сортировка - это способ пойти, а затем захватить верхнюю часть 3. Однако если в сортированную коллекцию есть вставка O (log N), вам придется делать это N раз или делать a O (NlogN) sort (который, кстати, является наихудшим сценарием N^2), вы получаете эффективность NlogN в отличие от простой O (N) итерации по массиву с max1/max2/max3, например, Riley выше. Сортировка или вставка в сортированную коллекцию проще всего, но не самая эффективная.

Answer 9

Построение на Райли логики, которая пропущена рассмотрение для дублированных элементов в верхнем положении 3, вот что я предлагаю, чтобы исправить эту проблему:

int max1 = Integer.MIN_VALUE; 
int max2 = Integer.MIN_VALUE; 
int max3 = Integer.MIN_VALUE; // assuming integer elements in the array 

for (int i = 0; i < theArray.length; i++) { 
    if (theArray[i] > max1) { 
     max3 = max2; 
     max2 = max1; 
     max1 = theArray[i]; 
    } else if (theArray[i] > max2) { 
     if (max1 == theArray[i]) { 
      // Neglect as already present in max1 
     } else { 
      max3 = max2; 
      max2 = theArray[i]; 
     } 
    } else if (theArray[i] > max3) { 
     if (max1 == theArray[i] || max2 == theArray[i]) { 
      // Neglect as already present in max1 OR max2 
     } else { 
      max3 = theArray[i]; 
     } 
    } 
}     

Answer 10

#include <stdio.h> 
#include <stdlib.h> 

int main() 
{ 
    int a[10] = {-10,50,200,30,45,70,780,850,10,900}; 
    int i=0; 
    int Max[3]={0}; 
    for(i=0;i<10;i++){ 
     if(Max[2]<a[i]) 
      Max[2] = a[i]; 
    } 
    for(i=0;i<10;i++){ 
     if(Max[1]<a[i] && a[i]<Max[2]) 
      Max[1] = a[i]; 
    } 
    for(i=0;i<10;i++){ 
     if(Max[0]<a[i] && a[i]<Max[1]) 
      Max[0] = a[i]; 
    } 
    printf("%d %d %d",Max[2],Max[1],Max[0]); 
    return 0; 
}