Оптимизация кода по времени выполнения

#python #алгоритм #python_36

Есть совершенно несложная по сути задачка с таким условием:
Дан массив a из n целых чисел. Напишите программу, которая найдет число, которое
встречается в массиве наибольшее число раз (взято отсюда: https://contest.yandex.ru/contest/12341/enter/).
Я недавно начал учить питон, смог придумать такое решение, которое очевидно не оптимальное,
но точно должно быть верным:

n=int(input())
a=[int(j) for j in input().split()]
b={}
for i in a:
    b[i]=b.get(i, 0)+1
for k, v in sorted(b.items(), reverse=True):
    if b[k]==max(b.values()):
        print(k)
        break


Проблема заключается в том, что на задачу также накладывается ограничение по времени
(2 секунды) и памяти (256Mb). Можете ли вы подсказать, с помощью каких методов можно
улучшить/оптимизировать решение?

Edit: Да, виноват, что сразу не отметил, при нескольких элементах, встречающихся
одинаково часто, вывести надо наибольший
    

Ответы

Ответ 1

Можно еще попробовать вариант с вычислительной сложностью O(n), требование по памяти
O(m), где m - число уникальных элементов и m <= n:

def my_mode(nums):
    r = {}
    max_cnt = -9999999999999999999999999999
    max_num = -9999999999999999999999999999

    for i in nums:
        r[i] = r.get(i, 0) + 1
        if r[i] > max_cnt:
            max_cnt = r[i]
            max_num = i
        elif r[i] == max_cnt:
            if i > max_num:
                max_num = i
    return max_num


Тесты:

In [156]: my_mode([2,1,2,1,3])
Out[156]: 2

In [157]: my_mode([2,1,2,1,1,3])
Out[157]: 1

In [158]: my_mode([3,2,1])
Out[158]: 3


Ответ 2

Пример с использованием collections.Counter:

In [107]: nums = [random.randint(0, 10**5) for _ in range(10**6)]

In [108]: len(nums)
Out[108]: 1000000

In [109]: from collections import Counter

In [110]: c = Counter(nums)

In [111]: c.most_common(1)
Out[111]: [(40945, 27)]

In [112]: c.most_common(1)[0][0]
Out[112]: 40945

In [113]: %timeit Counter(nums).most_common(1)[0][0]
238 ms ± 38.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)