Временная сложность Top K частых элементов в Python (Leetcode) ⇐ Python

[Гость]

Я пытаюсь найти более эффективное решение проблемы 347 в Leetcode. Мое решение оказалось не таким эффективным. Я не понимаю, почему это решение выполняется за время O(n).

Код: Выделить всё

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# count up the frequencies of each number: # O(n)
counts = {}
for n in nums:
counts[n] = 1 + counts.get(n, 0) # add one to the count, default if not found is 0

# create our buckets: O(n)
freq_buckets = for [[] for i in range(len(nums) + 1)]

# add the counts to each of the buckets
for num, count in counts.items():
# for that specific frequency, add this num to the list of
# numbers occurring at that frequency
freq_buckets[count].append(num)

# hold our k most frequent
most_frequent = []
# iterate from most frequent to least frequent
for i in range(len(freq_buckets) - 1, 0, -1): # O(n): loop 3
for num in freq_buckets[i]: # O(n): loop 4
most_frequent.append(num)

# break when we have k most frequent
if len(most_frequent) == k:
return most_frequent

На мгновение я поверил, что он выполняется за O(kn), потому что цикл 3 будет выполняться только до k . Однако при дальнейшем рассмотрении я вижу, что существует баланс между циклом 3 и циклом 4, поскольку если внешний цикл выполняется n итераций, то внутренний цикл может выполняться от 0 до n + 1 раз. Это наводит меня на мысль, что если внутренний цикл выполняется n раз, то мы должны быть в сегменте 1, что означает, что мы выполнили итерацию по внешнему циклу почти n раз, а затем повторили итерацию. во внутреннем цикле k раз (что может быть равно n, если n = k).
Есть случаи, с которыми я борюсь чтобы рассуждать.
Прав ли я, полагая, что этот алгоритм не работает за время O(n)? Если нет, объясните, почему.
Я пытался проанализировать временную сложность каждой строки и ожидал найти O(n).
Я также прочитал здесь еще один пост, но не понимаю, как они пришли к такому выводу.

Подробнее здесь: https://stackoverflow.com/questions/782 ... n-leetcode