Самый быстрый способ найти все индексы максимального значения в списке - Python

Question

У меня есть список, который выглядит следующим образом

input_list= [2, 3, 5, 2, 5, 1, 5]

Я хочу получить все индексы максимального значения. Нужно эффективное решение. Вывод будет следующим.

output = [2,4,6] (The above list 5 is maximum value in a list)

Я пытался с помощью кода ниже

m = max(input_list)
output = [i for i, j in enumerate(a) if j == m]

Мне нужно найти любое другое оптимальное решение.

Answer 1

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

Так что я не уверен, что вы можете сделать это быстрее, чем O(n) с помощью подхода списка.

Answer 2

Вот подход, который описан в комментариях. Даже если вы используете какую-то библиотеку, для решения этой проблемы вам, по крайней мере, придется пройти хотя бы один раз (considering input list is unsorted). Таким образом, даже нижняя граница для алгоритма будет Omega (size_of_list). Если список отсортирован, мы можем использовать binary_search для решения проблемы.

def max_indexes(l): 
     try: 
         assert l != [] 
         max_element = l[0] 
         indexes = [0] 
         for index, element in enumerate(l[1:]): 
             if element > max_element: 
                 max_element = element 
                 indexes = [index + 1] 
             elif element == max_element: 
                 indexes.append(index + 1) 
         return indexes 
     except AssertionError: 
         print ('input_list in empty')

Answer 3

Используйте цикл for для O(n) и итерируйте один раз по разрешению списка:

from itertools import islice

input_list= [2, 3, 5, 2, 5, 1, 5]

def max_indexes(l):
    max_item = input_list[0]
    indexes = [0]
    for i, item in enumerate(islice(l, 1, None), 1):
        if item < max_item:
            continue
        elif item > max_item:
            max_item = item
            indexes = [i]
        elif item == max_item:
            indexes.append(i)
    return indexes

Здесь у вас есть живой пример

Answer 4

 from collections import defaultdict
 dic=defaultdict(list)
 input_list=[]
 for i in range(len(input_list)):
         dic[input_list[i]]+=[i]

 max_value = max(input_list)

 Sol = dic[max_value]

Answer 5

Вы можете использовать numpy (numpy массивы очень быстрые ):

import numpy as np
input_list= np.array([2, 3, 5, 2, 5, 1, 5])
i, = np.where(input_list == np.max(input_list))
print(i)

Вывод:

[2 4 6]