Python 算法基础篇之列表

一、列表的本质动态数组1.1 不要被名字迷惑Python 的list不是链表Linked List而是动态数组Dynamic Array—— 是一段连续内存中存储的变长序列。内存布局示意 索引: 0 1 2 3 4 5 ┌──────┬──────┬──────┬──────┬──────┬──────┐ 值: │ 10 │ 20 │ 30 │ 40 │ 50 │ 60 │ └──────┴──────┴──────┴──────┴──────┴──────┘ ↑ ↑ 起始地址 已用末尾 ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ 预分配: │ 已用 │ 已用 │ 已用 │ 已用 │ 已用 │ 已用 │ 空闲 │ 空闲 │ └──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘ 当前容量 capacity 8关键特性元素在内存中连续存储→ 支持 O(1) 随机访问容量capacity≥ 长度size→ 预留空间减少扩容频率扩容时重新分配内存批量复制元素→ 均摊 O(1) 尾部插入1.2 操作复杂度速查操作示例时间复杂度原因索引访问lst[i]O(1)连续内存地址直接计算尾部追加lst.append(x)O(1)均摊预分配空间偶尔扩容尾部弹出lst.pop()O(1)直接缩减长度头部插入lst.insert(0, x)O(n)所有元素后移头部弹出lst.pop(0)O(n)所有元素前移中间插入lst.insert(i, x)O(n)后半部分元素后移中间删除lst.pop(i)/del lst[i]O(n)后半部分元素前移查找元素x in lstO(n)线性扫描获取长度len(lst)O(1)维护长度变量⚠️关键警示pop(0)和insert(0, x)是 O(n) 操作频繁头部操作请用collections.deque。二、基础操作创建与访问2.1 创建列表的六种方式# 方式1字面量最常用lst1[1,2,3,4,5]# 方式2list() 构造函数lst2list(range(5))# [0, 1, 2, 3, 4]lst3list(abc)# [a, b, c]# 方式3列表推导式Pythoniclst4[x**2forxinrange(5)]# [0, 1, 4, 9, 16]# 方式4乘法初始化注意陷阱lst5[0]*5# [0, 0, 0, 0, 0]# ⚠️ 陷阱[[]] * 3 创建3个引用同一列表的引用wrong[[]]*3wrong[0].append(1)# [[1], [1], [1]] —— 不是预期的[[1], [], []]# 正确做法列表推导式创建独立对象correct[[]for_inrange(3)]correct[0].append(1)# [[1], [], []] ✅# 方式5从可迭代对象生成lst6list(map(int,[1,2,3]))# [1, 2, 3]# 方式6条件过滤lst7[xforxinrange(10)ifx%20]# [0, 2, 4, 6, 8]2.2 索引与切片Python 最强大的序列操作lst[0,1,2,3,4,5,6,7,8,9]# 基础索引lst[0]# 0 —— 第一个lst[-1]# 9 —— 最后一个lst[3]# 3 —— 正数索引从0开始# 切片 [start:end:step]lst[2:5]# [2, 3, 4] —— 左闭右开lst[:3]# [0, 1, 2] —— 从头开始lst[7:]# [7, 8, 9] —— 到末尾lst[:]# [0..9] —— 复制整个列表lst[::2]# [0, 2, 4, 6, 8] —— 步长2lst[::-1]# [9, 8, ..., 0] —— 反转lst[8:3:-1]# [8, 7, 6, 5, 4] —— 反向切片# 切片赋值原地修改lst[2:5][20,30]# [0, 1, 20, 30, 5, 6, 7, 8, 9]lst[::2][0,0,0,0,0]# 步长切片赋值长度必须匹配# 删除切片dellst[2:5]# 删除索引2到4的元素切片索引的心算公式lst[start:end:step] - step 0从左到右取 start ≤ i end - step 0从右到左取 start ≥ i end - 省略 startstep0时从0开始step0时从末尾开始 - 省略 endstep0时到末尾step0时到开头三、添加与删除算法场景中的选择3.1 尾部操作O(1) 的黄金区域lst[1,2,3]# 追加单个元素lst.append(4)# [1, 2, 3, 4] —— O(1) 均摊# 追加多个元素可迭代对象lst.extend([5,6])# [1, 2, 3, 4, 5, 6] —— O(k)k为追加数量# 合并两个列表创建新列表new_lstlst[7,8]# O(nk)空间 O(nk)# 弹出尾部lastlst.pop()# 返回 6lst 变为 [1, 2, 3, 4, 5] —— O(1)3.2 头部与中间操作O(n) 的陷阱lst[1,2,3,4,5]# 头部插入O(n) —— 所有元素后移lst.insert(0,0)# [0, 1, 2, 3, 4, 5]# 中间插入O(n-i)i为插入位置lst.insert(3,99)# [0, 1, 2, 99, 3, 4, 5]# 头部弹出O(n)firstlst.pop(0)# 返回 0O(n)# 中间删除O(n-i)lst.pop(3)# 删除索引3的元素返回 99# 按值删除O(n) 查找 O(n) 删除lst.remove(3)# 删除第一个值为3的元素找不到抛 ValueError算法场景中的替代方案需求列表操作问题替代方案频繁头部插入/删除insert(0)/pop(0)O(n)collections.deque频繁中间插入/删除insert(i)/pop(i)O(n)链表 / 跳表频繁查找 删除remove(x)O(n)哈希表 / 集合维护有序序列sort()bisectO(n) 插入bisect模块 list3.3 删除所有匹配元素的正确姿势# ❌ 错误遍历中删除会导致索引错乱lst[1,2,1,3,1]fori,xinenumerate(lst):ifx1:lst.pop(i)# 漏删索引后移导致跳过元素# ✅ 正确1倒序删除不影响前面元素的索引lst[1,2,1,3,1]foriinrange(len(lst)-1,-1,-1):iflst[i]1:lst.pop(i)# [2, 3]# ✅ 正确2列表推导式过滤创建新列表lst[1,2,1,3,1]lst[xforxinlstifx!1]# [2, 3]# ✅ 正确3while remove删除所有匹配直到找不到lst[1,2,1,3,1]while1inlst:lst.remove(1)# [2, 3]但 O(n²)大数据量慎用四、列表推导式Python 的算法加速器4.1 基础语法# 基本形式[x**2forxinrange(5)]# [0, 1, 4, 9, 16]# 带条件过滤[xforxinrange(20)ifx%30]# [0, 3, 6, 9, 12, 15, 18]# 多重循环笛卡尔积[(i,j)foriinrange(3)forjinrange(3)]# [(0,0), (0,1), (0,2), (1,0), ..., (2,2)]# 带 else 的三元表达式[evenifx%20elseoddforxinrange(5)]# [even, odd, even, odd, even]4.2 算法中的应用LeetCode 1. 两数之和用列表推导式快速生成结果deftwo_sum(nums:list[int],target:int)-list[int]:seen{}# 值 → 索引fori,numinenumerate(nums):complementtarget-numifcomplementinseen:return[seen[complement],i]seen[num]ireturn[]矩阵转置一行代码matrix[[1,2,3],[4,5,6]]transposed[[row[i]forrowinmatrix]foriinrange(len(matrix[0]))]# [[1, 4], [2, 5], [3, 6]]扁平化嵌套列表nested[[1,2],[3,4],[5,6]]flat[xforsublistinnestedforxinsublist]# [1, 2, 3, 4, 5, 6]4.3 性能对比推导式 vs 循环importtime n1_000_000# 方式1for循环starttime.time()result1[]foriinrange(n):result1.append(i*2)t1time.time()-start# 方式2列表推导式starttime.time()result2[i*2foriinrange(n)]t2time.time()-start# 方式3mapstarttime.time()result3list(map(lambdax:x*2,range(n)))t3time.time()-startprint(ffor循环:{t1:.3f}s)print(f列表推导:{t2:.3f}s)# 通常最快print(fmap:{t3:.3f}s)结论列表推导式通常比for循环快 1.5~2 倍字节码优化比maplambda更易读。五、排序与搜索算法核心5.1 内置排序Timsortlst[3,1,4,1,5,9,2,6]# 原地排序稳定排序O(n log n)lst.sort()# [1, 1, 2, 3, 4, 5, 6, 9]lst.sort(reverseTrue)# [9, 6, 5, 4, 3, 2, 1, 1]# 按自定义key排序words[banana,pie,Washington,book]words.sort(keylen)# [pie, book, banana, Washington] —— 按长度# 返回新列表不修改原列表new_lstsorted(lst,keylambdax:-x)# 降序# 多条件排序students[(Alice,25),(Bob,20),(Alice,20)]students.sort(keylambdax:(x[0],x[1]))# 先按名字再按年龄Timsort 特性稳定排序相等元素保持原相对顺序最坏 O(n log n)最好 O(n)已接近有序时混合了归并排序和插入排序5.2 二分查找bisect 模块importbisect lst[1,3,3,5,7,9]# 查找插入位置保持有序bisect.bisect_left(lst,3)# 1 —— 3的左侧插入位置bisect.bisect_right(lst,3)# 3 —— 3的右侧插入位置bisect.bisect(lst,3)# 3 —— 同 bisect_right# 插入并保持有序O(n)因为需要移动元素bisect.insort_left(lst,4)# [1, 3, 3, 4, 5, 7, 9]bisect.insort_right(lst,3)# [1, 3, 3, 3, 4, 5, 7, 9]应用场景维护动态有序列表频繁查询排名/前驱/后继。六、深拷贝与浅拷贝隐蔽的bugimportcopy# 浅拷贝复制容器不复制内部对象lst1[[1,2],[3,4]]lst2lst1.copy()# 或 lst1[:], list(lst1)lst2[0][0]99print(lst1)# [[99, 2], [3, 4]] —— 被修改了# 深拷贝递归复制所有对象lst3copy.deepcopy(lst1)lst3[0][0]100print(lst1)# [[99, 2], [3, 4]] —— 不受影响# 不可变元素的列表浅拷贝足够simple[1,2,3]s_copysimple.copy()s_copy[0]99print(simple)# [1, 2, 3] —— 不受影响判断标准列表元素是否可变列表、字典、对象是 → 需要深拷贝。七、列表 vs 其他数据结构场景列表替代方案原因频繁尾部操作✅ 列表—O(1) 均摊频繁头部操作❌ O(n)dequeO(1) 双端频繁中间插入/删除❌ O(n)链表O(1) 已知位置频繁查找❌ O(n)set/dictO(1) 哈希维护有序 动态插入⚠️ O(n)bisect 列表折中方案不可变序列—tuple安全、可哈希八、算法实战列表在 LeetCode 中的应用8.1 双指针技巧defremove_duplicates(nums:list[int])-int: 26. 删除有序数组中的重复项 双指针慢指针指向写入位置快指针扫描 ifnotnums:return0slow0forfastinrange(1,len(nums)):ifnums[fast]!nums[slow]:slow1nums[slow]nums[fast]returnslow1# 新长度8.2 前缀和defsubarray_sum(nums:list[int],k:int)-int: 560. 和为 K 的子数组 前缀和 哈希表 fromcollectionsimportdefaultdict countdefaultdict(int)count[0]1prefix0ans0fornuminnums:prefixnum anscount[prefix-k]count[prefix]1returnans8.3 滑动窗口defmax_sliding_window(nums:list[int],k:int)-list[int]: 239. 滑动窗口最大值 单调队列 fromcollectionsimportdeque result[]qdeque()# 存索引保持单调递减fori,numinenumerate(nums):whileqandq[0]i-k:q.popleft()whileqandnums[q[-1]]num:q.pop()q.append(i)ifik-1:result.append(nums[q[0]])returnresult九、核心心法1. 复杂度条件反射看到pop(0)立即想到 O(n)看到append()想到 O(1) 均摊。这是写出高效 Python 算法的第一步。2. 推导式优先能用列表推导式就不用 for 循环能用生成器表达式就不用列表推导式大数据量时省内存。3. 选择正确的工具只读序列 →tuple频繁两端操作 →deque频繁查找 →set/dict有序维护 →bisectlist或sortedcontainers4. 避免拷贝陷阱[[]] * n是引用复制lst.copy()是浅拷贝嵌套结构需要deepcopy。判断标准当你能在写代码时自动规避pop(0)本能地用推导式替代循环并在看到维护有序动态数组时想到bisect——列表才真正成为你的本能。