LeetCode 347解决方案时间复杂性计算

Question

我一直在关注Neetcode，并处理了几个Leetcode问题。在347上，他建议他的解决方案是O(n(，但我很难真正分解出解决方案来确定为什么是这样。我觉得这是因为嵌套的for循环只运行到len(answers) == k。

我首先得到了每一行的时间复杂性，前几行是O(n(或O(1(，这是有道理的。一旦我进入嵌套的for循环，我就被抛弃了，因为内部循环将为每个外部循环迭代运行，并导致O(n*m(或类似性质的结果，这是有意义的。这就是我认为返回条件的限制因子作为循环迭代的上限的地方，因为一旦答案数组长度等于k，我们总是会返回(而且，在这个问题中，我们保证有一个唯一的答案(。最让我失望的是，我默认认为任何嵌套的for循环都将是O(n^2(，这似乎并不罕见，但似乎不是每次都是这样。

有人能告诉我我的建议是否正确吗？你会怎么分解？

class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:

countDict = {}

frequency = [[] for i in range(len(nums)+1)]

for j in nums:
countDict[j] = 1 + countDict.get(j, 0)  

for c, v in countDict.items():
frequency[v].append(c)

answer = []

for n in range(len(frequency)-1, 0, -1):
for q in frequency[n]:
print(frequency[n])
answer.append(q)
if len(answer) == k:
return answer

Answer 1

frequency是元素频率和原始列表中的值之间的映射。frequency中的总元素数始终等于或小于nums中的原始项数(因为它映射到nums中的唯一值(。

即使存在嵌套循环，它仍然只在某些O(C*n)总值上迭代，其中C <= 1等于O(n)。

---

注意，使用一些基本的助手可以很容易地清理这个答案。计数器可以为您获取countDict的原始映射。可以使用defaultdict来构造frequency。然后，您可以将frequencydict值展平，并对最终结果进行切片。

from collections import Counter, defaultdict

class Solution:
def top_k_frequent(self, nums: list[int], k: int) -> list[int]:
counter = Counter(nums)
frequency = defaultdict(list)
for num, freq in counter.items():
frequency[freq].append(num)
sorted_nums = []
for freq in sorted(frequency, reverse=True):
sorted_nums += frequency[freq]
return sorted_nums[:k]

这是一种有趣的方法，可以在一行中完成！

class Solution:
def top_k_frequent(self, nums: list[int], k: int) -> list[int]:
return sorted(set(nums), key=Counter(nums).get, reverse=True)[:k]