4

Есть совершенно несложная по сути задачка с таким условием:
Дан массив 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: Да, виноват, что сразу не отметил, при нескольких элементах, встречающихся одинаково часто, вывести надо наибольший

7
  • Какие есть ограничения на n?
    – Yaant
    25 апр 2019 в 16:11
  • Не больше 300 000
    – magik2
    25 апр 2019 в 16:12
  • 1
    Гугл мне подсказывает (сам я python не знаю), что в питоне есть специальный тип коллекций - Counter и даже с методом most_common(). Мне кажется, оно там должно быть достаточно оптимизировано, чтобы с запасом уложиться в указанные лимиты, тем более, что 300 000 - это не так много.
    – Yaant
    25 апр 2019 в 16:19
  • да, кстати, можно ли пользоваться библиотеками и функцией max()? 25 апр 2019 в 16:20
  • Интерпретатор python используется в т.н. дефолтной сборке, то есть Counter, наверно, должен быть. Функция не должна вызывать проблем точно
    – magik2
    25 апр 2019 в 16:27

2 ответа 2

2

Можно еще попробовать вариант с вычислительной сложностью 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
5
  • Этот алгоритм не более линейный, чем тот, что используется в Counter (в среднем линейный). Но этот код однозначно медленнее, просто потому, что код Counter написан на си, и менее универсальный - работает только с числами.
    – extrn
    25 апр 2019 в 18:29
  • @extrn, я по-моему нигде не утверждал, что этот алгоритм "самый линейный" алгоритм в мире (кстати мне нравится ваша классификация линейности алгоритмов: более линейный, в среднем линейный, etc.) :) Разумеется эта реализация будет работать медленнее, по сравнению с реализацией на C. Код будет работать не только с числами: my_mode(['a','c','b','c','b']) 25 апр 2019 в 18:41
  • просто не хотелось употреблять более витиеватые термины. На счет только чисел согласен, погорячился, смутила инициализация max_num числом. оно ни на что не влияет.
    – extrn
    25 апр 2019 в 18:54
  • @extrn, а зачем вы свой ответ удалили? По-моему, многим будет интересно узнать о функции statistics.mode().... 25 апр 2019 в 18:57
  • 1
    ради ачивки, очевидно же :)
    – extrn
    25 апр 2019 в 19:01
1

Пример с использованием 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)
1
  • Спасибо, я постараюсь разобраться, с подключением модулей пока мало работал. Не подскажете, к какому источнику лучше всего обращаться при самостоятельном изучении: есть ли какие-то хорошие учебники или сайты?
    – magik2
    25 апр 2019 в 16:53

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.