LeetCode 347题解时间复杂度为何是O(n)？求拆解验证

你的猜测完全正确——嵌套循环确实会在len(answer) == k时提前终止，这也是整个解法时间复杂度能达到O(n)的关键原因之一。下面我们逐段拆解代码的时间复杂度：

代码回顾 #

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

逐段复杂度分析 #

1. 统计元素频率

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

   这段代码遍历nums数组一次，每个元素的字典操作（get和赋值）都是O(1)常数时间，因此时间复杂度为O(n)，其中n是nums的长度。

2. 填充频率分组数组

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

   这里遍历的是countDict的所有键值对，键的数量等于nums中不同元素的数量（记为m，m ≤ n）。每个append操作是O(1)，所以这部分时间复杂度为O(m)，由于m≤n，可简化为O(n)。

3. 收集前k高频元素
   这是你困惑的嵌套循环部分：

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

   核心关键点：frequency数组中所有子数组的元素总数等于m（每个不同元素仅被放入一个子数组）。外层循环从高频率到低频率遍历，内层循环遍历对应频率的元素列表。

   由于我们一旦收集到k个元素就直接返回，内层循环的总迭代次数最多为k次（k ≤ m ≤ n）。就算不考虑提前终止，两层循环的总迭代次数也只是m次，不会超过n次。因此这部分时间复杂度依然是O(n)。

总时间复杂度 #

将三部分的时间复杂度相加：O(n) + O(n) + O(n) = O(n)，完全符合NeetCode给出的结论。

需要纠正的误区：嵌套循环≠O(n²)复杂度，只有当内外层循环的迭代次数独立且均为O(n)时，才会达到O(n²)。本题中嵌套循环的总迭代次数被严格限制在n以内，因此属于线性复杂度。

内容的提问来源于stack exchange，提问作者dSisk