CS Mistakes

---

M-CS-001 - 嵌套循环重复计算复杂度

Date: 2026-08-14

Related:

• Time Complexity

Problem

for i in range(n):
    for j in range(i):
        ...

My Wrong Reasoning

先认为外层为 O(n)。

然后计算：

$$1+2+\cdots +n=O(n^2)$$

又错误地乘了一次外层 O(n)，得到 O(n³)。

Correct Reasoning

求和：

$$\sum _{i=0}^{n-1}i$$

本身已经统计了所有外层迭代产生的内层总操作次数。

因此：

$$O(n^2)$$

Error Type

复杂度分析 / 重复计算

Trigger

看到：

for i ...
    for j in range(i)

不能机械乘复杂度，应首先考虑求总操作次数。

---

M-CS-002 - Two Sum错误理解Hash

Date: 2026-08-14

Related:

• Hash Table
• Set / Map

Wrong Idea

曾尝试将：

target = 9

作为 Hash 取模的基数，从余数关系寻找两数和。

Correct Pattern

遍历当前元素：

x

计算：

complement = target - x

查询：

complement in seen

Hash Table 的作用是：

将“以前是否出现过 complement”的查询由 O(n) 降为平均 O(1)。

推荐的一遍 Map 状态设计：

key   = 已出现的数
value = 下标

Error Type

Hash 算法应用

---

M-CS-003 - 第 K 大在 Min Heap 中的位置判断错误

Date: 2026-08-20

Related:

• Heap / Priority Queue

Problem

使用大小为 K 的 Min Heap 维护数组中最大的 K 个元素时：

最终第 K 大元素在哪里？

My Wrong Answer

曾回答：

在叶子节点

Correct Reasoning

大小为 K 的 Min Heap 最终保存的是：

整体最大的 K 个元素

Min Heap 的堆顶是这 K 个元素中的最小值，因此：

Min Heap top
= Top-K 中最小的
= 整体第 K 大

例如最大的 3 个元素为：

10, 15, 20

则大小为 3 的 Min Heap 的堆顶为：

10

也就是整体第 3 大。

叶子节点之间没有全局大小顺序，因此不能通过“叶子位置”直接确定第 K 大。

Correct Pattern

Top K largest → size-K Min Heap
K-th largest  → Min Heap top

Error Type

Heap / Top-K 极值位置

Trigger

看到“大小为 K 的 Min Heap 保存 Top-K largest”时，立即问：

这 K 个候选里最小的是谁？

答案就是堆顶，也就是整体第 K 大。