определение count_dominators(items). Поиск доминаторов в списке. Как сделать это более эффективным?

#python #performance #loops #time

#python #Производительность #циклы #время

Вопрос:

Мне была задана проблема, в которой мне нужно найти количество доминаторов в списке. Вот описание проблемы.И вот что я придумал: мое решение.

Из того, что я могу сказать, код работает, но когда он доходит до очень больших чисел, таких как финальный тест, требуется много времени, чтобы вернуть что-либо. Я почти уверен, что есть способ свести это к одному циклу, но я понятия не имею, как это сделать.

1. Вы пробовали читать второй абзац описания назначения? Вы пытались перейти по ссылке там, чтобы получить общее представление о том, почему возникает проблема с производительностью?

2. Подсказка: если вы уже знали, что определенный элемент является доминатором, не могли бы вы использовать эту информацию, чтобы быстрее определить, являются ли некоторые другие элементы доминаторами? Как?

3. Привет, добро пожаловать в SO. Не могли бы вы включить свой код в виде текста в публикацию. Таким образом, другим пользователям было бы проще помочь вам (я думаю, nowbody действительно любит набирать код со скриншотов).

Ответ №1:

существует линейное решение, я надеюсь, что вы сможете его использовать.

таким образом, указатель перемещается от конца к началу, и если найти новый максимум, счетчик (n) плюс один.

 def count(lst):
    if lst == []:
        return 0
    lst.reverse()

    max_i = lst[0]
    n = 1
    for x in lst:
        if x > max_i:
            max_i = x
            n  = 1
    return n