0 Basic

矩阵索引

1matrix[i][j]
2matrix[i][0] # 第i行第一个
3matrix[0][j] # 第j列第一个

原生list没有列的概念：

1matrix[:, j]     # TypeError: list indices must be integers or slices, not tuple
2matrix[:][j]     # 不报错,但取到的是第 j 行,而且改的是临时副本

嵌套 list 是一维列表装着 m 个互不相干的行对象引用,每行甚至可以长度不同:

1[[1, 2, 3], [4], [5, 6]]   # 完全合法

1row = row[::-1]   # ✗ 只是把局部名字 row 重新绑定到新列表,matrix 纹丝不动
2row.reverse()     # ✓ 原地反转,改的是对象本身
3matrix[i][:] = [0]*n   # ✓ 先索引到真实行对象,再对它的切片赋值 → 原地
4matrix[:][i] = [0]*n   # ✗ 先切片(造新对象)再索引 → 改的是临时对象

1 Matrix

1.1 矩阵置零 | Medium

题目: 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。要求原地算法。进阶:使用 O(1) 额外空间

思路分析：把判断动作和修改动作分开，先判断后单独修改

plan 1：朴素做法

分别记录所有要置0的行和列，用set去重
针对这些行和列，分别置0

plan 2：O(1)

读取边界
先在内部打标记后修改
最后处理边界

踩坑记录：

1matrix[row][:] = [0] * n # ✅
2matrix[:][col] = [0] * m # ❌

rows and cols应该用set()
any()用法

代码：

 1class Solution:
 2    def setZeroes(self, matrix: List[List[int]]) -> None:
 3        m , n = len(matrix), len(matrix[0])
 4        rows, cols = set(), set()
 5
 6        for i in range(m):
 7            for j in range(n):
 8                if matrix[i][j] == 0:
 9                    rows.add(i)
10                    cols.add(j)
11
12        for row in rows:
13            matrix[row][:] = [0] * n
14
15        for col in cols:
16            for i in range(m):
17                matrix[i][col] = 0

 1class Solution:
 2    def setZeroes(self, matrix: List[List[int]]) -> None:
 3        m, n = len(matrix), len(matrix[0])
 4        row0 = any(matrix[0][j] == 0 for j in range(n))
 5        col0 = any(matrix[i][0] == 0 for i in range(m))
 6
 7        for i in range(1, m):
 8            for j in range(1, n):
 9                if matrix[i][j] == 0:
10                    matrix[i][0] = 0
11                    matrix[0][j] = 0
12
13        for i in range(1, m):
14            for j in range(1, n):
15                if matrix[i][0] == 0 or matrix[0][j] == 0:
16                    matrix[i][j] = 0
17
18        if row0:
19            matrix[0][:] = [0] * n
20        if col0:
21            for i in range(m):
22                matrix[i][0] = 0

复杂度：

plan 1:

时间O(mn)
空间O(m + n)

plan 2:

时间O(mn)
空间O(1)

1.2 螺旋矩阵 | Medium

题目: 给你一个 m 行 n 列的矩阵,按照顺时针螺旋顺序返回矩阵中的所有元素。

输入: [[1,2,3],[4,5,6],[7,8,9]]
输出: [1,2,3,6,9,8,7,4,5]

思路分析：

维护 top / bottom / left / right 四条边界,每轮走完最外圈的四条边, 然后四个边界各向内挪一格,循环处理下一圈。走完一圈后剩下的子矩阵, 递归般地重复同样的四步。
- 上：[left, right] $\Rightarrow$ range(left, right + 1)
- 右：[top + 1, bottom] $\Rightarrow$ range(top + 1, bottom + 1)
- 下：[right - 1, left, -1] $\Rightarrow$ range(right - 1, left - 1, -1)
- 左：[bottom - 1, top - 1, -1] $\Rightarrow$ range(bottom - 1, top, -1)
假如只有一行或者一列，所以：

1if left < right and top < bottom:

踩坑记录：

while 用 <=,if 用 <,不能混
倒序 range 的终点要多减 1

1range(right - 1, left - 1, -1)     # 终点写 left-1 才能取到 left
2range(bottom - 1, top, -1)         # 终点写 top 才能停在 top+1

代码：

 1class Solution:
 2    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
 3        m, n = len(matrix), len(matrix[0])
 4        top, bottom, left, right = 0, m - 1, 0, n - 1
 5        res = []
 6
 7        while top <= bottom and left <= right:
 8            for j in range(left, right + 1):
 9                res.append(matrix[top][j])
10            for i in range(top + 1, bottom + 1):
11                res.append(matrix[i][right])
12
13            if top < bottom and left < right:
14                for j in range(right - 1, left - 1, -1):
15                    res.append(matrix[bottom][j])
16                for i in range(bottom - 1, top, -1):
17                    res.append(matrix[i][left])
18            top, bottom, left, right = top + 1, bottom - 1, left + 1, right - 1
19
20        return res

复杂度：

时间 O(mn):每个元素恰好访问一次
空间 O(1):除输出数组外只有四个边界变量

1.3 旋转图像 | Medium

题目: 给定一个 n x n 的二维矩阵表示一个图像,将图像顺时针旋转 90 度。必须原地旋转,不能使用另一个矩阵。

思路分析：

顺时针旋转 90° = 转置 + 每行反转
逆时针旋转 90° = 转置 + 每列反转
180 = 每行反转 + 每列反转

踩坑记录：

转置必须从i + 1开始

代码：

 1class Solution:
 2    def rotate(self, matrix: List[List[int]]) -> None:
 3        """
 4        Do not return anything, modify matrix in-place instead.
 5        """
 6        n = len(matrix)
 7        for i in range(n):
 8            for j in range(i + 1, n):
 9                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
10
11        for row in matrix:
12            row.reverse()

手写反转版(不依赖 list.reverse):

1for i in range(n):
2    l, r = 0, n - 1
3    while l < r:
4        matrix[i][l], matrix[i][r] = matrix[i][r], matrix[i][l]
5        l += 1
6        r -= 1

复杂度：

时间 O(n²):转置约 n²/2 次交换, 反转约 n²/2 次
空间 O(1):全程只有元组交换用的临时槽位

1.4 搜索二维矩阵 II | Meidum

题目: 搜索 m x n 矩阵中的目标值 target,矩阵满足:

每行元素从左到右升序
每列元素从上到下升序

思路分析：站在右上角 (0, n-1),两个可移动方向的单调性正好相反:

向左走,值一定变小(行内升序)
向下走,值一定变大(列内升序)

踩坑记录：

循环条件两个方向不对称

1while i < m and j >= 0:

代码：

 1class Solution:
 2    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
 3        m, n = len(matrix), len(matrix[0])
 4        i, j = 0, n - 1
 5        while i < m and j >= 0:
 6            if matrix[i][j] == target:
 7                return True
 8            elif matrix[i][j] < target:
 9                i += 1
10            else:
11                j -= 1
12        return False

复杂度：

时间 O(m + n):每一步必定让 i 加一或 j 减一,总步数不超过 m+n
空间 O(1)

2 Array

2.1 轮转数组 | Medium

题目: 给定整数数组 nums,将元素向右轮转 k 个位置,k 非负。要求原地修改。

1 <= nums.length <= 1e5,0 <= k <= 1e5
示例:[1,2,3,4,5,6,7], k=3 → [5,6,7,1,2,3,4]

思路分析：

向右轮转 k 位 = 把后 k 个元素整体搬到前面

踩坑记录：

k %= n 必须写。k <= 1e5 但 n 可能只有 1,不取模直接越界

代码：

直接翻转：

1class Solution:
2    def rotate(self, nums: List[int], k: int) -> None:
3        n = len(nums)
4        k %= n
5        nums[:] = nums[-k:] + nums[:-k]

三次翻转：

 1class Solution:
 2    def rotate(self, nums: List[int], k: int) -> None:
 3        n = len(nums)
 4        k %= n
 5
 6        def reverse(l: int, r: int) -> None:
 7            while l < r:
 8                nums[l], nums[r] = nums[r], nums[l]
 9                l += 1
10                r -= 1
11
12        reverse(0, n - 1)
13        reverse(0, k - 1)
14        reverse(k, n - 1)

复杂度：

拼接翻转：

时间：O(n)
空间：O(n)

三次翻转：

时间：O(n)
空间：O(1)

2.2 合并区间 | Medium

题目: intervals[i] = [start_i, end_i],合并所有重叠区间,返回不重叠的区间数组。

1 <= intervals.length <= 1e4,0 <= start_i <= end_i <= 1e4
相接也算重叠:[1,4] 与 [4,5] → [1,5]

思路分析：

区间题的万能第一步:按左端点排序。排完序后,能与当前区间合并的一定紧挨在它后面,于是只需一次线性扫描
维护结果数组 res,每次拿新区间 [s, e] 和 res[-1] 比较:
- s <= res[-1][1] → 有交集,合并:res[-1][1] = max(res[-1][1], e)
- 否则 → 断开了,res.append([s, e])

踩坑记录：

end 必须取 max,不能写 res[-1][1] = e。反例 [[1,10],[2,3]]:直接赋值会得到 [1,3],吞掉大区间

代码：

 1class Solution:
 2    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
 3        intervals.sort(key=lambda x: x[0])
 4        res = []
 5
 6        for st, ed in intervals:
 7            if res and res[-1][1] >= st:
 8                res[-1][1] = max(ed, res[-1][1])
 9            else:
10                res.append([st, ed])
11
12        return res

复杂度：

时间 O(n log n),瓶颈在排序,扫描只有 O(n)
空间 O(log n),排序递归栈;不计返回值

2.3 找到所有数组中消失的数字 | Easy

题目: 含 n 个整数的数组 nums,1 <= nums[i] <= n。找出 [1, n] 内所有没出现在 nums 中的数字。进阶:不使用额外空间且时间 O(n)(返回数组不算额外空间)。

思路分析：

答案一定在[1, n]之间，所以我们可以建立一个标记数组表示这个数字是否出现过：seen = [0] * (n + 1)，这样的空间复杂度为O(n)
我们也可以利用数组本身作为标记，如负号标记法：约定 nums[i] < 0 表示 i+1 出现过

踩坑记录：

1nums[idx] = -1                    # ✗
2nums[idx] = -abs(nums[i])         # ✗ 等价于 -(idx+1),同样是常数
3nums[idx] = -abs(nums[idx])       # ✓

nums 既是记账本又是还没读完的数据源。冲掉一格,后面读到它时读出的是假值,会到处打假勾,而真正的数字永远没被记录

代码：

1class Solution:
2    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
3        n = len(nums)
4        seen = [0] * (n + 1)
5
6        for num in nums:
7            seen[num] = 1
8
9        return [i for i in range(1, n + 1) if seen[i] == 0]

1class Solution:
2    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
3        n = len(nums)
4        for num in nums:
5            idx = abs(num) - 1
6            nums[idx] = -abs(nums[idx])
7        return [i+1 for i in range(n) if nums[i] > 0]

复杂度：

seen标记：

时间：O(n)
空间：O(n)

负号标记法：

时间：O(n)
空间：O(n)

2.4 缺失的第一个正数 | Hard

题目: 未排序整数数组,找出没有出现的最小正整数。要求时间 O(n)、常数级额外空间。

1 <= nums.length <= 1e5,-2^31 <= nums[i] <= 2^31 - 1

思路分析：

答案 ∈ [1, n+1]，数组长 n,最好情况是恰好装着 1..n,答案为 n+1;只要有任何一格被负数、0 或大于 n 的数占了,1..n 里必然空出一个坑，依然使用nums本身作为标记，采用负号标记法

踩坑记录：

清场写成 < 0,漏掉 0

1if nums[i] < 0:      # ✗ 0 躲过清场
2    nums[i] = n + 1

需要检查索引合法

代码：

 1class Solution:
 2    def firstMissingPositive(self, nums: List[int]) -> int:
 3        n = len(nums)
 4
 5        for i in range(n):
 6            if nums[i] <= 0:
 7                nums[i] = n + 1
 8
 9        for num in nums:
10            idx = abs(num) - 1
11            if 0 <= idx < n:
12                nums[idx] = -abs(nums[idx])
13
14        for i in range(n):
15            if nums[i] > 0:
16                return i + 1
17
18        return n + 1
19

复杂度：

时间O(n)
空间O(1)

0 Basic#

1 Matrix#

2 Array#

0 Basic

1 Matrix

2 Array