Можно ли получить 2 самых больших числа в списке, используя один проход?

Question

Можно ли найти 2 самых больших числа в массиве и выполнить цикл по коллекции только один раз?

У меня был вопрос для собеседования, и я не получил его вовремя.

Answer 1

Это кажется довольно простым ..

int[] nums = { 3, 1, 4, 1, 5, 9, 2, 6 };

int max1 = -1;
int max2 = -1;
foreach (int num in nums)
{
  if (num > max1) { max2 = max1; max1 = num; }
  else if (num > max2) { max2 = num; }
}    

Например:

// 3: max2 = -1; max1 = 3;
// 1: max2 = 1;
// 4: max2 = 3; max1 = 4;

Быстрое объяснение:

• Определить -1 как заполнитель, можетиспользуйте int.MinValue или, что еще лучше, отдельное значение bool для указания отсутствия совпадения
• Если проверенное значение больше текущего максимума (max1), присвойте текущий максимум max2, новое значение max1
• Иначе, если должно быть меньше, но если оно больше второго максимума, присвойте новое значение max2

Answer 2

В общем, вы можете найти K самых больших (или самых маленьких) чисел в массиве, используя один проход для любого K. Общая сложность времени будет O (NK), где N - размер массива:

Хранить отсортированный список чисел, который имеет не более K элементов. Пройдите через массив и для каждого элемента:

1. , если список еще не заполнен, вставить элемент
2. В противном случае, если элемент больше, чем наименьший элемент в списке, вставьте этот элемент и удалите наименьший.

В конце концов, список будет содержать K самых больших элементов, что мы и хотели.

Это решение довольно медленное, хотя. Используя самобалансирующееся двоичное дерево поиска или список пропусков, вы можете добраться до O (N log K). (Поскольку в общем случае сортировка невозможна быстрее, чем O (N log N), и этот метод можно использовать для сортировки всего массива, если мы установим K = N, это выглядит как лучшее, что мы можем получить.)

В случае K = 2 вам не нужна вся эта тяжелая техника. Достаточно двух переменных, представляющих две позиции в списке.

Answer 3

Да, это так. Просматривая список, сохраняйте запись самого большого найденного числа и всякий раз, когда вы найдете большее число, сохраняйте самое большое найденное во второй по величине найденный перед обновлением самого большого найденного. Если значение больше второго по величине, обновите второе по величине значение.