Как повысить эффективность сравнения элементов списка?

Question

Всякий раз, когда я кодирую на онлайн-платформах и каким-то образом мне приходится сравнивать элементы списка друг с другом, я использую следующий код, который, по моему мнению, является наиболее эффективным из возможных. Это последний код, который я практиковал. Он должен был найти максимальный индекс между двумя одинаковыми элементами.

max=0
for i in range(len(mylist)):
    if max==(len(mylist)-1):
        break
    for j in range(i + 1, len(mylist)):
        if mylist[i] == mylist[j]:
            if max>(abs(i-j)):
                max=abs(i-j)

Он запускает большинство тестовых случаев, но иногда он показывает «превышен лимит времени». Я знаю, что это связано с ограничениями и сложностью времени, но я все еще не могу найти лучший путь. Если бы кто-нибудь мог мне помочь, это было бы здорово.

Answer 1

Вы можете сгруппировать по равным элементам, а затем найти разницу в группе и сохранить максимум:

lst = [1, 3, 5, 3, 7, 8, 9, 1]

groups = {}
for i, v in enumerate(lst):
    groups.setdefault(v, []).append(i)

result = max(max(group) - min(group) for group in groups.values())

print(result)

Выход

7

Сложностьэтот подход O(n).

Answer 2

def get_longest_distance_between_same_elements_in_list(mylist):

    positions = dict()
    longest_distance = 0

    if len(mylist) < 1:
        return longest_distance

    for index in range(0, len(mylist)):
        if mylist[index] in positions:
            positions[mylist[index]].append(index)
        else:
            positions[mylist[index]] = [index]

    for key, value in positions.items():
        if len(value) > 1 and longest_distance < value[len(value)-1] - value[0]:
            longest_distance = value[len(value)-1] - value[0]

    return longest_distance


l1 = [1, 3, 5, 3, 7, 8, 9, 1]
l2 = [9]
l3 = []
l4 = [4, 4, 4, 4, 4]
l5 = [10, 10, 3, 4, 5, 4, 10, 56, 4]
print(get_longest_distance_between_same_elements_in_list(l1))
print(get_longest_distance_between_same_elements_in_list(l2))
print(get_longest_distance_between_same_elements_in_list(l3))
print(get_longest_distance_between_same_elements_in_list(l4))
print(get_longest_distance_between_same_elements_in_list(l5))

Выход -

7                                                                                                                                                                                  
0                                                                                                                                                                                  
0                                                                                                                                                                                  
4                                                                                                                                                                                  
6

Сложность времени: O (n)

Answer 3

В Python проще использовать функции на основе Си. Также не называйте переменные типы Python, такие как list.

x = [item for i, item in enumerate(l) if item in l[i+1:]]
# do something with list of values