数组
数组的数据结构¶
数组 = 同类型元素在一整块连续内存 → 计算地址 =
起始地址 + index × 元素大小，随机访问 O(1)。Python 真正的“连续数组”：
array.array('i')、bytes/bytearray、memoryview、numpy.ndarray； Pythonlist只是连续的 指针槽位，元素对象本身散落各处。优势与代价：
- 连续存储带来高速缓存友好、随机访问快；
- 长度固定，插入/删除需搬迁数据，扩容需整块重拷。
一、数组的基础知识
- 数组的本质
数组是一种：
- 连续内存
- 支持随机访问
- 下标访问 O(1)
的数据结构。
核心特点：
- 通过索引访问元素：nums[i]
- 插入删除（中间位置）需要移动元素
- 数组的时间复杂度特性
设数组长度为 n：
- 访问元素：O(1)
- 修改元素：O(1)
- 末尾添加：O(1)（均摊）
- 中间插入：O(n)
- 中间删除：O(n)
算法题中常见考点：
- 双指针
- 滑动窗口
- 前缀和
- 二分查找
- 原地修改
- 单调栈（数组作为底层容器）
二、Python 中的数组实现
Python 没有“真正的 C 风格数组”，常用两种：
1️⃣ list（算法题首选）
本质是动态数组（Dynamic Array）。
特点：
- 自动扩容
- 随机访问 O(1)
- 适合绝大多数算法题
创建：
nums = [1, 2, 3]
nums = []
nums = [0] * n
2️⃣ array 模块（几乎不用在算法题）
import array
arr = array.array('i', [1,2,3])
用于类型受限的高效存储，但算法题基本不用。
结论：
Hot100 全部用 list。
三、Python 数组常见语法总结
1️⃣ 访问与修改
nums[i]
nums[i] = x
2️⃣ 遍历方式
最常用：
for x in nums:
带索引：
for i in range(len(nums)):
推荐更 Pythonic：
for i, x in enumerate(nums):
3️⃣ 添加与删除
尾部添加：
nums.append(x)
尾部删除：
nums.pop()
指定位置删除：
nums.pop(i)
插入：
nums.insert(i, x)
⚠ 插入/中间删除是 O(n)
4️⃣ 切片（高频）
nums[l:r]
nums[::-1]
注意：
切片会创建新数组，空间 O(k)
拼接
nums_copy = nums_1 +nums_2
时间复杂度：O(n + k)
会新建列表并复制全部元素。
5️⃣ 排序
nums.sort() # 原地
nums.sort(reverse=True)
sorted_nums = sorted(nums) # 返回新数组
时间复杂度：
O(n log n)
6️⃣ 常见初始化技巧
二维数组：
matrix = [[0]*n for _ in range(m)]
⚠ 不要写：
matrix = [[0]*n]*m # 错误，会共享引用
四、算法题中数组的核心技巧
1️⃣ 双指针
- 左右夹逼
- 快慢指针
典型题：
- 两数之和 II
- 移动零
- 盛最多水的容器
2️⃣ 滑动窗口
- 连续子数组问题
- 子串问题
典型：
- 最长无重复子串
- 最小覆盖子串
3️⃣ 前缀和
用于快速区间求和：
prefix[i] = nums[0] + ... + nums[i-1]
4️⃣ 原地修改
很多题要求 O(1) 空间：
- 旋转数组
- 移动零
- 删除重复元素
五、数组的空间本质
Python list：
- 底层是连续内存
- 存储的是“对象引用”
- 扩容时会申请更大空间并复制
因此：
- 访问快
- 扩容有均摊成本
六、数组类题目核心思维
数组题的关键不是语法，而是：
- 是否有单调性？
- 是否可以双指针？
- 是否可以滑动窗口？
- 是否可以排序后再做？
- 是否可以前缀和优化？
七、复杂度总结
| 操作 | 时间复杂度 |
|---|---|
| 访问 | O(1) |
| 修改 | O(1) |
| append | O(1) 均摊 |
| 插入 | O(n) |
| 删除 | O(n) |
| 排序 | O(n log n) |
空间复杂度：
O(n)
八、一句话总结
在 Hot100 中：
数组 = Python list 核心能力 = 双指针 + 滑动窗口 + 原地修改 + 前缀思想
In [ ]:
Copied!
a = [1001, 1003, 1002, 1004, 1005]
for i, v in enumerate(a):
print(f"Index: {i}, id: {id(a[i])}")
a = [1001, 1003, 1002, 1004, 1005]
for i, v in enumerate(a):
print(f"Index: {i}, id: {id(a[i])}")
Index: 0, id: 2327529914480 Index: 1, id: 2327529916272 Index: 2, id: 2327529916304 Index: 3, id: 2327529916208 Index: 4, id: 2327529916048
53.最大子数组和¶
给定整数数组 nums，求连续子数组（至少包含一个元素）的 最大和
In [ ]:
Copied!
from typing import List
class Solution:
"核心思想——“如果当前累加的和变成了负数，就抛弃它”，复杂度O（n）"
def maxSubArray(self, nums: List[int]) -> int:
max_score = cur_score = nums[0]
for i in range(1, len(nums)):
cur_score = nums[i] if cur_score < 0 else cur_score + nums[i]
max_score = max(max_score, cur_score)
return max_score
a = [10, -11, -6, 17, -10, -10, 12]
b = Solution()
print(b.maxSubArray(a))
from typing import List
class Solution:
"核心思想——“如果当前累加的和变成了负数，就抛弃它”，复杂度O（n）"
def maxSubArray(self, nums: List[int]) -> int:
max_score = cur_score = nums[0]
for i in range(1, len(nums)):
cur_score = nums[i] if cur_score < 0 else cur_score + nums[i]
max_score = max(max_score, cur_score)
return max_score
a = [10, -11, -6, 17, -10, -10, 12]
b = Solution()
print(b.maxSubArray(a))
17
In [ ]:
Copied!
class Solution:
def maxSubArray(self, nums) -> int:
cur_sum = 0
max_sum = nums[0]
for num in nums:
cur_sum = max(cur_sum + num, num)
max_sum = max(max_sum, cur_sum)
return max_sum
a = [10, -11, -6, 17, -10, -10, 12]
b = Solution()
print(b.maxSubArray(a))
class Solution:
def maxSubArray(self, nums) -> int:
cur_sum = 0
max_sum = nums[0]
for num in nums:
cur_sum = max(cur_sum + num, num)
max_sum = max(max_sum, cur_sum)
return max_sum
a = [10, -11, -6, 17, -10, -10, 12]
b = Solution()
print(b.maxSubArray(a))
17
时间复杂度分析
该算法只对数组进行了一次线性遍历。循环从索引 1 到 n−1，每一步只包含常数次比较与加法操作，不存在嵌套循环或递归。因此，整体时间复杂度为 O(n)，其中 n 是数组长度。
空间复杂度分析
算法只使用了两个变量 cur_score 和 max_score 来维护当前子数组和与全局最大值，没有使用额外的数组或递归调用栈，输入数组本身也未被复制。因此，额外空间复杂度为 O(1)。
总结
- 时间复杂度：O(n)
- 空间复杂度：O(1)
该实现即经典的 Kadane 算法，其本质是通过“当前和为负则舍弃”的贪心策略，在一次遍历中完成最大子数组和的计算。
56.合并区间¶
给定区间集合 [1 , 3] , [2 , 6] , [8 , 10] , [15 , 18]。 已按左端点从小到大排序，下面按步骤合并。
解题思路：
初始化
- 把
intervals[0] = [1, 3]加入答案，作为当前正在合并的区间。 - 现在 合并区间 = [1 , 3]。
- 把
处理
intervals[1] = [2, 6]- 左端点
2 ≤ 3，与当前区间重叠 → 可合并。 - 更新右端点：
max(3, 6) = 6 - 合并区间变为 [1 , 6]（左端点无需改动）。
- 左端点
处理
intervals[2] = [8, 10]- 左端点
8 > 6，与当前区间不重叠 → 不能合并。 - [1 , 6] 已确定，加入答案；开始新的合并区间 [8 , 10]。
- 左端点
处理
intervals[3] = [15, 18]- 左端点
15 > 10，仍不重叠。 - [8 , 10] 固定并加入答案；最后把 [15 , 18] 作为新合并区间加入。
- 左端点
最终结果 [[1, 6], [8, 10], [15, 18]]
语法知识：
lambda x: x[0]：定义一个匿名函数，接收参数 x，返回 x[0]
sort(key = 一个函数)
当intervals.sort(key = function)时，进行如下计算。
for 每个元素 e in intervals:
计算 key(e)In [ ]:
Copied!
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x: x[0])
output = [intervals[0], ]
for i in intervals[1:]:
last_interval = output[-1]
if last_interval[-1] >= i[0]:
last_interval[-1] = max(last_interval[-1], i[-1])
else:
output.append(i)
return output
a = [[1,3],[2,6],[8,10],[15,18]]
b = Solution()
print(b.merge(a))
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda x: x[0])
output = [intervals[0], ]
for i in intervals[1:]:
last_interval = output[-1]
if last_interval[-1] >= i[0]:
last_interval[-1] = max(last_interval[-1], i[-1])
else:
output.append(i)
return output
a = [[1,3],[2,6],[8,10],[15,18]]
b = Solution()
print(b.merge(a))
[[1, 6], [8, 10], [15, 18]]
复杂度分析：
时间复杂度由两部分构成。首先对区间数组按起点排序，排序复杂度为 O(n log n)，其中 n 是区间数量；随后进行一次线性扫描并合并区间，遍历过程中每个区间只处理一次，时间复杂度为 O(n)。因此整体时间复杂度为 O(n log n)，由排序步骤主导。
空间复杂度方面，算法使用了一个结果列表 output 来存储合并后的区间。在最坏情况下（区间完全不重叠），output 需要存放 n 个区间，因此额外空间复杂度为 O(n)。若不将返回结果计入额外空间，则除排序可能使用的内部栈空间外，算法本身只使用常数级辅助变量。
189.轮转数组¶
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
核心思路:
1.把整个数组反转
2.反转前 k 个元素
3.反转后 n-k 个元素，三次反转即可把后 k 个元素移到前面，实现向右轮转。
In [ ]:
Copied!
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k%n
def reverse(left, right):
right = right - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, n)
reverse(0, k)
reverse(k, n)
a = [1,2,3,4,5,6,7]
b = Solution()
b.rotate(a, 3)
print(a)
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k%n
def reverse(left, right):
right = right - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
reverse(0, n)
reverse(0, k)
reverse(k, n)
a = [1,2,3,4,5,6,7]
b = Solution()
b.rotate(a, 3)
print(a)
[5, 6, 7, 1, 2, 3, 4]
复杂度分析：
该算法通过三次区间反转完成数组旋转。每一次 reverse 操作都在指定区间内进行首尾交换，区间长度分别为 n、k 和 n−k，但三次反转中所有元素被交换的总次数与 n 成正比，因此整体时间复杂度为 O(n)。
算法只使用了少量临时变量（用于元素交换和指针移动），未创建任何新的数组或递归结构，除输入数组本身外不占用额外存储空间，因此空间复杂度为 O(1)。
238.除以自身以外数组的乘积¶
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
核心思想： 用“前缀积 × 后缀积”替代除法。对每个下标 i，答案是 nums 左边所有元素乘积（前缀积）与右边所有元素乘积（后缀积）的乘积。
用输出数组本身存前缀积，再用一个常量变量滚动后缀积
首扫：顺序遍历，把 i 左侧元素乘积直接写进
ans[i]。次扫：逆序遍历，用变量
R累乘右侧元素；边更新R边把结果乘回ans[i]。 这样只额外用到一个整数R，把额外空间降到 O(1)（题目默认不计输出数组）。相当于把ans作为原来的左缀积L，而R实时更新，从右到左，直接乘到ans上
In [ ]:
Copied!
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
# 前缀积：i 从 1 开始，跳过 0
for i in range(1, n):
ans[i] = ans[i-1] * nums[i-1]
# 后缀积：i 从 n-1 到 0，必须含 0
R = 1
for i in range(n-1, -1, -1):
ans[i] *= R # 先用
R *= nums[i] # 再乘
return ans
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
# 前缀积：i 从 1 开始，跳过 0
for i in range(1, n):
ans[i] = ans[i-1] * nums[i-1]
# 后缀积：i 从 n-1 到 0，必须含 0
R = 1
for i in range(n-1, -1, -1):
ans[i] *= R # 先用
R *= nums[i] # 再乘
return ans
复杂度
- 时间：两次线性遍历 → O(n)
- 空间：只用常量→ O(1) 额外空间（不含输出数组）
41.缺失的第一个正数¶
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
原地哈希法核心思想 将数组本身当作哈希表，用索引位置表示数字，用符号表示该数字是否存在
- 索引 i 代表数字 i+1
- 负数表示该位置对应的数字存在
- 正数表示该位置对应的数字不存在
关键注意点
- 符号处理
- 读取时：必须用
abs(nums[i])获取原始数值 - 标记时：用
-abs(nums[num-1])确保变为负数，避免重复标记
- 边界控制
- 范围检查：只处理
1 ≤ num ≤ n的数字 - 预处理：将
n+1作为占位符，因为它不会影响 [1,n] 的标记
- 映射关系
- 数字 x → 索引 x-1
- 索引 i → 数字 i+1
举例演示
原数组: [3, 4, -1, 1] (n=4)
步骤1: [3, 4, 5, 1] # -1改为5
步骤2:
- 看到3，标记索引2：[3, 4, -5, 1]
- 看到4，标记索引3：[3, 4, -5, -1]
- 看到5，超出范围，跳过
- 看到1，标记索引0：[-3, 4, -5, -1]
步骤3: 索引1为正数，返回 1+1 = 2
核心优势：O(1) 空间复杂度，充分利用数组索引和符号的双重信息。
In [ ]:
Copied!
def firstMissingPositive(nums):
n = len(nums)
# 第一步：将所有非正数和大于n的数改为n+1
# 这样确保数组中只有[1,n+1]范围内的数
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
# 第二步：利用符号标记存在性
# 对于数字x，将索引x-1位置的数字标记为负数
for i in range(n):
index = abs(nums[i]) #因为下面的操作会将nums[i]的值由正变负，所以需要取绝对值
if index <= n:
nums[index - 1] = -abs(nums[index - 1])
# 第三步：找到第一个正数的位置
for i in range(n):
if nums[i] > 0:
return i + 1
# 如果所有位置都被标记了，说明[1,n]都存在
return n + 1
a = [3, 4, -1, 1]
print(firstMissingPositive(a))
def firstMissingPositive(nums):
n = len(nums)
# 第一步：将所有非正数和大于n的数改为n+1
# 这样确保数组中只有[1,n+1]范围内的数
for i in range(n):
if nums[i] <= 0:
nums[i] = n + 1
# 第二步：利用符号标记存在性
# 对于数字x，将索引x-1位置的数字标记为负数
for i in range(n):
index = abs(nums[i]) #因为下面的操作会将nums[i]的值由正变负，所以需要取绝对值
if index <= n:
nums[index - 1] = -abs(nums[index - 1])
# 第三步：找到第一个正数的位置
for i in range(n):
if nums[i] > 0:
return i + 1
# 如果所有位置都被标记了，说明[1,n]都存在
return n + 1
a = [3, 4, -1, 1]
print(firstMissingPositive(a))
2
复杂度分析：
该算法对数组进行了三次线性遍历，每一次遍历中仅包含常数次操作（比较、取绝对值、赋值），不存在嵌套循环或递归。因此，整体时间复杂度为 O(n)，其中 n 为数组长度。
空间复杂度方面，算法直接在原数组 nums 上进行数值覆盖与符号标记，仅使用了少量临时变量（如 n、i、num），未引入额外的辅助数组或递归栈。因此，额外空间复杂度为 O(1)。
不符合空间复杂度要求，但简单的做法：哈希表
hashset = set(nums) 需要遍历一次 nums，设数组长度为 n，则时间复杂度为 O(n)，其空间复杂度为 O(n)。 while循环查询操作，时间复杂度最坏情况为O(n)。
In [ ]:
Copied!
class Solution:
def firstMissingPositive(self, nums):
hashset = set(nums)
i = 1
while i in hashset:
i += 1
return i
a = [3, 4, -1, 1]
print(Solution().firstMissingPositive(a))
class Solution:
def firstMissingPositive(self, nums):
hashset = set(nums)
i = 1
while i in hashset:
i += 1
return i
a = [3, 4, -1, 1]
print(Solution().firstMissingPositive(a))
2
73. 矩阵置零¶
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
核心思想总结：
第一行和第一列作为“行标记”和“列标记”的存储空间。
先记录第一行、第一列是否本身含 0（防止被覆盖）。
再利用其余位置标记。
最后统一根据标记进行清零。
本质是把额外的 O(m+n) 标记空间压缩到矩阵内部。
In [ ]:
Copied!
from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
原地修改矩阵，使得如果一个元素为 0，
则其所在行和列全部置为 0。
"""
m = len(matrix)
n = len(matrix[0])
# -----------------------------
# 1. 判断第一行和第一列是否原本含有 0, 行或列中存在为0的，那么后续就需要对其行和列变为0
# -----------------------------
first_row_zero = False
first_col_zero = False
# 检查第一行
for j in range(n):
if matrix[0][j] == 0:
first_row_zero = True
break
# 检查第一列
for i in range(m):
if matrix[i][0] == 0:
first_col_zero = True
break
# -----------------------------
# 2. 使用第一行和第一列作为标记位
# -----------------------------
# 遍历除第一行和第一列之外的元素
# 如果 matrix[i][j] == 0
# 则标记 matrix[i][0] 和 matrix[0][j]
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# -----------------------------
# 3. 根据标记，将内部元素置 0
# -----------------------------
# 如果某行被标记（matrix[i][0] == 0）
# 或某列被标记（matrix[0][j] == 0）
# 则该位置置 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# -----------------------------
# 4. 处理第一行
# -----------------------------
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
# -----------------------------
# 5. 处理第一列
# -----------------------------
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
matrix = [
[1,1,1],
[1,0,1],
[1,1,1]
]
Solution().setZeroes(matrix)
print(matrix)
from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
原地修改矩阵，使得如果一个元素为 0，
则其所在行和列全部置为 0。
"""
m = len(matrix)
n = len(matrix[0])
# -----------------------------
# 1. 判断第一行和第一列是否原本含有 0, 行或列中存在为0的，那么后续就需要对其行和列变为0
# -----------------------------
first_row_zero = False
first_col_zero = False
# 检查第一行
for j in range(n):
if matrix[0][j] == 0:
first_row_zero = True
break
# 检查第一列
for i in range(m):
if matrix[i][0] == 0:
first_col_zero = True
break
# -----------------------------
# 2. 使用第一行和第一列作为标记位
# -----------------------------
# 遍历除第一行和第一列之外的元素
# 如果 matrix[i][j] == 0
# 则标记 matrix[i][0] 和 matrix[0][j]
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# -----------------------------
# 3. 根据标记，将内部元素置 0
# -----------------------------
# 如果某行被标记（matrix[i][0] == 0）
# 或某列被标记（matrix[0][j] == 0）
# 则该位置置 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# -----------------------------
# 4. 处理第一行
# -----------------------------
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
# -----------------------------
# 5. 处理第一列
# -----------------------------
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
matrix = [
[1,1,1],
[1,0,1],
[1,1,1]
]
Solution().setZeroes(matrix)
print(matrix)
In [ ]:
Copied!
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
first_row_zero = False
first_col_zero = False
m = len(matrix)
n = len(matrix[0])
for i in range(m):
if matrix[i][0] == 0:
first_col_zero = True
break
for j in range(n):
if matrix[0][j] ==0:
first_row_zero = True
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] =0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
first_row_zero = False
first_col_zero = False
m = len(matrix)
n = len(matrix[0])
for i in range(m):
if matrix[i][0] == 0:
first_col_zero = True
break
for j in range(n):
if matrix[0][j] ==0:
first_row_zero = True
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] =0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
时间复杂度：
第一次扫描第一行：O(n)
第一次扫描第一列：O(m)
扫描内部元素两次：O(mn)
总体时间复杂度为：
O(mn)
因为主导项仍然是矩阵遍历。
空间复杂度：
仅使用：
两个布尔变量 first_row_zero 和 first_col_zero
因此空间复杂度为：
O(1)
满足题目“原地算法”的要求。
54. 螺旋矩阵¶
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
该问题本质是“分层遍历矩阵”。 从最外层开始，一圈一圈向内收缩。
用四个边界变量控制当前遍历范围：
top：当前上边界
bottom：当前下边界
left：当前左边界
right：当前右边界
每一轮循环按顺时针顺序遍历四条边：
从左到右遍历上边界
从上到下遍历右边界
从右到左遍历下边界（前提：top ≤ bottom）
从下到上遍历左边界（前提：left ≤ right）
每遍历完一条边，就收缩对应边界。
关键点在于：
每遍历一条边后要更新边界
在遍历下边和左边时要做边界判断，防止重复遍历
In [ ]:
Copied!
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
res = []
# 定义四个边界
top, bottom = 0, m - 1
left, right = 0, n - 1
# 当边界没有交错时继续
while top <= bottom and left <= right:
# 1. 从左到右遍历上边界
for j in range(left, right + 1):
res.append(matrix[top][j])
top += 1
# 2. 从上到下遍历右边界
for i in range(top, bottom + 1):
res.append(matrix[i][right])
right -= 1
"""第 1 步和第 2 步是“消耗上边和右边”。
执行完这两步后，当前层可能已经完全遍历完。
第 3 步和第 4 步是“可选边”。
只有在仍然存在有效区域时才可以遍历，否则：
会重复访问
或逻辑上访问无效区域"""
# 3. 从右到左遍历下边界（必须判断）
if top <= bottom:
for j in range(right, left - 1, -1):
res.append(matrix[bottom][j])
bottom -= 1
# 4. 从下到上遍历左边界（必须判断）
if left <= right:
for i in range(bottom, top - 1, -1):
res.append(matrix[i][left])
left += 1
return res
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
print(Solution().spiralOrder(matrix))
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
res = []
# 定义四个边界
top, bottom = 0, m - 1
left, right = 0, n - 1
# 当边界没有交错时继续
while top <= bottom and left <= right:
# 1. 从左到右遍历上边界
for j in range(left, right + 1):
res.append(matrix[top][j])
top += 1
# 2. 从上到下遍历右边界
for i in range(top, bottom + 1):
res.append(matrix[i][right])
right -= 1
"""第 1 步和第 2 步是“消耗上边和右边”。
执行完这两步后，当前层可能已经完全遍历完。
第 3 步和第 4 步是“可选边”。
只有在仍然存在有效区域时才可以遍历，否则：
会重复访问
或逻辑上访问无效区域"""
# 3. 从右到左遍历下边界（必须判断）
if top <= bottom:
for j in range(right, left - 1, -1):
res.append(matrix[bottom][j])
bottom -= 1
# 4. 从下到上遍历左边界（必须判断）
if left <= right:
for i in range(bottom, top - 1, -1):
res.append(matrix[i][left])
left += 1
return res
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
print(Solution().spiralOrder(matrix))
时间复杂度：
O(mn)
矩阵中每个元素恰好被访问一次。
空间复杂度：
O(1)
除了返回结果列表外，只使用常数级变量。
48. 旋转图像¶
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
核心思路：
顺时针旋转 90° 本质等价于：
先沿主对角线转置 再将每一行左右翻转
In [ ]:
Copied!
from typing import List
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
原地将 n x n 矩阵顺时针旋转 90 度
"""
n = len(matrix)
# -----------------------------
# 1. 沿主对角线转置
# matrix[i][j] 和 matrix[j][i] 交换, 只需要遍历上三角区域（i < j）即可避免重复交换和跳过主对角线上的元素
# -----------------------------
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# -----------------------------
# 2. 每一行左右翻转
# -----------------------------
for i in range(n):
matrix[i].reverse()
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Solution().rotate(matrix)
print(matrix)
from typing import List
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
原地将 n x n 矩阵顺时针旋转 90 度
"""
n = len(matrix)
# -----------------------------
# 1. 沿主对角线转置
# matrix[i][j] 和 matrix[j][i] 交换, 只需要遍历上三角区域（i < j）即可避免重复交换和跳过主对角线上的元素
# -----------------------------
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# -----------------------------
# 2. 每一行左右翻转
# -----------------------------
for i in range(n):
matrix[i].reverse()
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Solution().rotate(matrix)
print(matrix)
In [ ]:
Copied!
from typing import List
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
原地将 n x n 矩阵顺时针旋转 90 度
"""
n = len(matrix)
# -----------------------------
# 1. 沿主对角线转置
# -----------------------------
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# -----------------------------
# 2. 手写每一行的左右翻转（双指针）
# -----------------------------
for i in range(n):
left = 0
right = n - 1
while left < right:
matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left]
left += 1
right -= 1
from typing import List
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
原地将 n x n 矩阵顺时针旋转 90 度
"""
n = len(matrix)
# -----------------------------
# 1. 沿主对角线转置
# -----------------------------
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# -----------------------------
# 2. 手写每一行的左右翻转（双指针）
# -----------------------------
for i in range(n):
left = 0
right = n - 1
while left < right:
matrix[i][left], matrix[i][right] = matrix[i][right], matrix[i][left]
left += 1
right -= 1
复杂度分析
时间复杂度：需要遍历矩阵上三角区域进行转置，然后再遍历整个矩阵翻转为O(n²)，行反转为O(n²)，整体时间复杂度为O(n²)
空间复杂度：只使用常数额外空间，满足原地要求。O(1)
240. 搜索二维矩阵 II¶
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
核心思路：
核心最优思路：从右上角（或左下角）开始搜索。
为什么选右上角？
设当前位置为 matrix[i][j]：
左边元素更小
下边元素更大
也就是说：
当前位置同时具备：
一维单调性（向左减小）
一维单调性（向下增大）
因此可以通过比较一次排除一整行或一整列。
In [ ]:
Copied!
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
# 从右上角开始
i, j = 0, n - 1
while i < m and j >= 0:
if matrix[i][j] == target:
return True
# 由于矩阵的行和列都是升序的，如果当前元素大于目标值，说明目标值不可能在当前列中（因为下面的元素更大），所以 j 减少 1，排除当前列。
elif matrix[i][j] > target:
j -= 1
# 由于矩阵的行和列都是升序的，如果当前元素小于目标值，说明目标值不可能在当前行中（因为右边的元素更大），所以 i 增加 1，排除当前行。
else:
i += 1 # 排除当前行
return False
matrix = [
[1,4,7,11,15],
[2,5,8,12,19],
[3,6,9,16,22],
[10,13,14,17,24],
[18,21,23,26,30]
]
target = 5
sol = Solution()
print(sol.searchMatrix(matrix, target))
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
# 从右上角开始
i, j = 0, n - 1
while i < m and j >= 0:
if matrix[i][j] == target:
return True
# 由于矩阵的行和列都是升序的，如果当前元素大于目标值，说明目标值不可能在当前列中（因为下面的元素更大），所以 j 减少 1，排除当前列。
elif matrix[i][j] > target:
j -= 1
# 由于矩阵的行和列都是升序的，如果当前元素小于目标值，说明目标值不可能在当前行中（因为右边的元素更大），所以 i 增加 1，排除当前行。
else:
i += 1 # 排除当前行
return False
matrix = [
[1,4,7,11,15],
[2,5,8,12,19],
[3,6,9,16,22],
[10,13,14,17,24],
[18,21,23,26,30]
]
target = 5
sol = Solution()
print(sol.searchMatrix(matrix, target))
复杂度分析
时间复杂度：
O(m + n)
因为： 每一步要么 i 增加 1， 要么 j 减少 1， 最多走 m + n 步。
空间复杂度：
O(1)
只使用常数变量。