Что лучший способ состоит в том, чтобы получить минимальное или максимальное значение от Массива чисел?

После чтения общих комментариев (спасибо за Ваш интерес) я нашел, что "лучший" путь (наименьшее количество объема кода, лучше всего работая), чтобы сделать это должно было просто отсортировать Массив, и затем захватить первое значение в Массиве:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

Это также работает на Массив Объектов - Вы просто используете Array.sortOn (), функционируют и определяют свойство:

// Sample data
var myArray:Array /* of XML */ = 
    [
    <item level="2" name="a" />
    <item level="3" name="b" />
    <item level="3" name="c" />
    <item level="2" name="d" />
    <item level="5" name="e" />
    ]

// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);

var lowestLevel:int = myArray[0].@level;

я надеюсь, что это помогает кому-то еще когда-нибудь!

Если Вы хотите найти и минуту и макс. одновременно, цикл может быть изменен следующим образом:

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

Это должно добраться, достигают O (n) синхронизация.

Примите во внимание, что сортировка массива только будет быстрее что цикличное выполнение до определенного размера массива. Если Ваш массив является небольшим (и он будет похож на то любое время), затем, Ваше решение прекрасно подходит. Но если это могло бы стать слишком большим, необходимо использовать условное выражение для использования подхода вида, когда массив является небольшим, и нормальное повторение, когда это слишком большое

Это зависит от требований к приложению реального мира.

, Если Ваш вопрос является просто гипотетическим, то основы были уже объяснены. Это - типичный поиск по сравнению с проблемой вида. Было уже упомянуто, что алгоритмически Вы не собираетесь достигать лучше, чем O (n) для того случая.

Однако при рассмотрении практического применения вещи становятся более интересными. Необходимо было бы тогда рассмотреть, насколько большой массив, и процессы, вовлеченные в добавление и удаление из набора данных. В этих случаях может быть лучше получить вычислительный 'удар' во вставке / время удаления путем сортировки на лету. Вставки в предварительный сортированный массив не являются настолько дорогими.

самый быстрый ответ запроса на запрос Min Max всегда будет от сортированного массива, потому что, поскольку другие упомянули, Вы просто берете первый или последний элемент - предоставление Вам O (1) стоимость.

Некоторое время больше технического объяснения на вычислительных затратах включенная, и Большая нотация O, проверьте статью Wikipedia здесь .

Nick.

Зависит от того, что Вы называете "лучше всего". С теоретической точки зрения Вы не можете решить проблему в [меньше чем 111] в детерминированной Машине Тьюринга.

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

struct MinMax{
   public int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   if (start == end)
      return new MinMax { Min = array[start], Max = array[start] };

   if (start == end - 1)
      return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;

   MinMax res1 = FindMinMax(array, start, (start + end)/2);
   MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
   return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

простое решение должно было бы отсортировать и получить первый и последний объект, хотя это является, очевидно, не самым быстрым;)

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

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

Если массив не отсортирован, это лучшее, Вы собираетесь добраться. Если это отсортировано, просто возьмите первые и последние элементы.

, Конечно, если это не отсортировано, затем сортируя сначала и захватив первое и последнее, как гарантируют, будет менее эффективным, чем просто цикличное выполнение до однажды. Даже лучшие алгоритмы сортировки должны посмотреть на каждый элемент несколько раз (в среднем O (зарегистрируйте N), времена для каждого элемента. Это - O (N*Log N) общее количество. Простое сканирование однажды через только O (N).

, Если Вы желаете быстрый доступ к самому большому элементу в структуре данных, смотрите на "кучу" для эффективного способа сохранить объекты в своего рода порядке.

Нет никакого надежного способа получить минимум/максимум, не тестируя каждое значение. Вы не хотите пробовать вид, или что-либо как этот, идя через массив является O (n), который лучше, чем какой-либо алгоритм сортировки может сделать в общем случае.

Если Вы создаете массив однажды и хотите найти максимум только однажды, итерация является лучшей, можно сделать.

, Когда Вы хотите изменить массив и иногда хотеть знать максимальный элемент, необходимо использовать Приоритетная Очередь . Одна из лучших структур данных для этого "куча" Fibonacci , если это слишком сложно, используют Двоичная "куча" , который медленнее, но все еще хорош.

Для нахождения минимума и максимума просто создайте две "кучи" и измените знак чисел в одном из них.

Если

1. Массив не отсортирован
2. Нахождение минимального и максимального значений выполняется одновременно

Тогда существует алгоритм, который находит минимальное и максимальное значение за 3n / 2 числа сравнения. Что нужно сделать, так это обработать элементы массива попарно. Большую часть пары следует сравнивать с текущим максимумом, а меньшую из пары следует сравнивать с текущим минимумом. Кроме того, нужно проявлять особую осторожность, если массив содержит нечетное количество элементов.

В коде C ++ (заимствованный код у Мехрдада).

struct MinMax{
   int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   MinMax  min_max;
   int index;
   int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
   if ( n%2 != 0 ){// if n is odd

     min_max.Min = array[start];
     min_max.Max = array[start];

     index = start + 1;
   }
   else{// n is even
     if ( array[start] < array[start+1] ){
       min_max.Min = array[start];
       min_max.Max = array[start+1];
     }
     else{
       min_max.Min = array[start+1];
       min_max.Max = array[start];
     }
     index = start + 2;
   }

   int big, small;
   for ( int i = index; i < n-1; i = i+2 ){
      if ( array[i] < array[i+1] ){ //one comparison
        small = array[i];
        big = array[i+1];
      }
      else{
        small = array[i+1];
        big = array[i];
      }
      if ( min_max.Min > small ){ //one comparison
        min_max.Min = small;
      }
      if ( min_max.Max < big ){ //one comparison
        min_max.Max = big;
      }
   }

   return min_max;
}

Очень легко увидеть, что количество необходимых сравнений равно 3n / 2. Цикл выполняется n / 2 раз, и на каждой итерации выполняется 3 сравнения. Вероятно, это оптимальный вариант. В настоящий момент я не могу указать на конкретный источник этого. (Но, думаю, где-то я видел доказательства этого. )

Рекурсивное решение, данное Мердадом выше, вероятно, также достигает этого минимального количества сравнений (последнюю строку необходимо изменить). Но с тем же числом сравнений итеративное решение всегда будет превосходить рекурсивное решение из-за накладных расходов при вызове функции, как он упомянул. Однако, если кто-то заботится только о поиске минимума и максимума нескольких чисел (как это делает Эрик Белэр), никто не заметит никакой разницы в сегодняшнем компьютере с любым из вышеперечисленных подходов. Для большого массива разница может быть значительной.

Хотя это решение и решение, данное Мэтью Брубакером, имеют сложность O (n), на практике следует тщательно оценивать задействованные скрытые константы. Количество сравнений в его решении 2n. Было бы заметно ускорение, полученное с помощью решения с 3n / 2 сравнениями по сравнению с 2n сравнениями.