Алгоритм поиска в массиве двух максимальных значений

#алгоритм #массивы #любой_язык

В результате нужно получить индексы ячеек массива с максимальными значениями.

Например, для массива arr[4, 50, 11, 20] это будут 1 и 3 (arr[1], arr[3]) - индексы
максимальных значений.
    

Ответы

Ответ 1

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

Вот вам псевдокод:

list maximalK = empty
// инвариант: maximalK содержит отсортированный список наибольших
// k из всех просмотренных элементов
foreach e in sourceList
    p = position of e in maximalK // (binary search)
    if (p >= k)
        continue
    insert e into maximalK at position p
    if maximalK.size > k
        remove last from maximalK


Заметьте, что при k == sourceList.size вы получаете просто алгоритм сортировки (бинарными)
вставками.

Временная сложность: O(n * k) (n — размер списка), за счёт сдвига при вставке. (Используя
sorted map для maximalK, можно уменьшить до O(n * log k).)