链表

定义

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

哨兵节点

  1. 说明：虚拟头节点是一个哨兵节点，它位于真正头节点的前面。在处理链表头可能被删除、修改或需要统一操作时，使用虚拟头节点可以避免单独处理头节点的特殊情况，使代码更简洁统一。
  2. 题型：几乎所有涉及链表头部可能变化的题目（如删除节点、反转部分链表、合并链表等）。
1
2
3
4
5
6
def dummy_example(head: ListNode) -> ListNode:
    dummy = ListNode(0)    # 创建虚拟头节点，值任意（通常为0）
    dummy.next = head      # 将虚拟头节点指向真正的头节点
    curr = dummy           # 当前指针从虚拟头开始
    # ... 进行操作，可能修改 curr.next 等
    return dummy.next      # 返回真正的头节点（虚拟头的下一个）

双指针

快慢指针

  1. 说明：快指针每次走两步，慢指针每次走一步。利用速度差可以找到中点、判断环等。
  2. 题型：寻找链表中点（力扣 876. 链表的中间结点），判断链表是否有环（力扣 141. 环形链表），在判断有环的基础上，进一步找到环的入口（力扣 142. 环形链表 II）
1
2
3
4
5
6
7
def f(head: ListNode) -> ListNode:
    slow = fast = head
    # 快指针每次走两步，慢指针每次走一步
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # 慢指针即为中点
1
2
3
4
5
6
7
8
def has_cycle(head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # 相遇说明有环
            return True
    return False
1
2
3
4
5
6
7
8
9
10
11
12
13
def detect_cycle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # 有环，进入第二阶段
            ptr = head
            while ptr != slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None

间隔指针

  1. 说明：两个指针保持固定间隔 k 同时移动，常用于找倒数第 k 个节点。
  2. 题型：寻找倒数第 k 个节点（力扣 面试题 02.02. 返回倒数第 k 个节点）
1
2
3
4
5
6
7
8
9
10
def find_from_end(head: ListNode, k: int) -> ListNode:
    p1 = p2 = head
    # p1 先走 k 步
    for _ in range(k):
        p1 = p1.next
    # 然后 p1 和 p2 一起走，直到 p1 走到末尾
    while p1:
        p1 = p1.next
        p2 = p2.next
    return p2.val

链表归并排序

  1. 说明：利用快慢指针找到链表中点，并将链表从中间断开，形成左右两个子链表。递归排序左右子链表。合并两个有序子链表，合并时借助哨兵节点简化操作。
  2. 题型：排序链表（力扣 148. 排序链表）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def sort_list(head: ListNode) -> ListNode:
    # 递归终止条件：链表为空或只有一个节点
    if not head or not head.next:
        return head

    # 1. 找到链表中间节点，并将链表从中间断开为左右两个子链表
    mid = get_middle(head)
    left = head
    right = mid.next
    mid.next = None          # 断开连接

    # 2. 递归排序左右子链表
    left = sort_list(left)
    right = sort_list(right)

    # 3. 合并两个有序子链表
    return merge_two_lists(left, right)

def get_middle(head: ListNode) -> ListNode:
    slow = head
    fast = head
    # 快指针每次走两步，慢指针每次走一步
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)       # 哨兵节点，简化边界处理
    curr = dummy              # 当前指针，指向合并链表的尾部

    # 同时遍历两个链表，将较小值的节点接到 curr 后面
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next

    # 处理剩余部分（最多一个链表还有剩余）
    curr.next = l1 if l1 else l2

    return dummy.next

栈

操作

  1. 入栈（push）：stack.append(x)，O(1)
  2. 出栈（pop）：stack.pop()，O(1)
  3. 查看栈顶（peek）：stack[-1]，O(1)
  4. 判空：not stack，O(1)

括号匹配

  1. 说明：查字符串中的括号是否合法匹配（如 ()、{}、[]），或计算最长有效括号的长度。核心思想是遇到左括号压栈，遇到右括号时检查栈顶是否匹配，匹配则弹出，否则无效。
  2. 题型：有效的括号（力扣 20. 有效的括号），最长有效括号（力扣 32. 最长有效括号）

有效的括号

  • 说明：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。使用栈：遇到左括号入栈，遇到右括号时检查栈顶是否与之匹配，若匹配则弹出，否则直接返回 False。遍历结束后栈应为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def is_valid(s: str) -> bool:
    # 括号映射：右括号 -> 对应的左括号
    mapping = {')': '(', '}': '{', ']': '['}
    stack = []
    for ch in s:
        if ch in mapping:                     # 当前字符是右括号
            if stack and stack[-1] == mapping[ch]:
                stack.pop()
            else:
                return False
        else:                                  # 当前字符是左括号
            stack.append(ch)
    # 栈空表示所有括号都正确匹配
    return not stack

最长有效括号

  • 说明：给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。一种方法是使用栈记录所有匹配括号对的索引，然后对这些索引排序，寻找最长的连续递增序列（相邻索引差 1），其长度即为最长有效括号的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def longest_valid_parentheses(s: str) -> int:
    n = len(s)
    stack = []          # 栈，存放左括号的索引
    matched_indices = []   # 记录所有匹配括号对的索引

    for i in range(n):
        if s[i] == ')':
            if stack and s[stack[-1]] == '(':
                matched_indices.append(stack.pop())
                matched_indices.append(i)
        else:  # s[i] == '('
            stack.append(i)

    # 将索引排序，以便寻找连续区间
    matched_indices.sort()

    max_len = 0
    i = 0
    while i < len(matched_indices):
        j = i + 1
        # 寻找连续递增的子序列（相邻索引差1）
        while j < len(matched_indices) and matched_indices[j] == matched_indices[j - 1] + 1:
            j += 1
        # 当前连续段的长度 = 元素个数
        max_len = max(max_len, j - i)
        i = j

    return max_len

单调栈

  1. 说明：栈内元素（通常存下标）保持单调递增或递减。例如找「下一个更大元素」时，维护一个递减栈（栈底到栈顶递减），意味着栈中元素都还没遇到比它们大的数。需要快速查找数组中每个元素左边或右边第一个比它大（或小）的元素。通过维护栈内元素的单调性（递增或递减），可以在一次遍历中得到答案。常用于解决“下一个更大元素”、“每日温度”、“接雨水”等问题。
  2. 题型：下一个更高温度出现在几天后（力扣 739. 每日温度），下一个更大元素（力扣 496. 下一个更大元素 I）接雨水（力扣 42. 接雨水（经典困难题，可用单调栈优化））

每日温度

  • 说明：给定一个温度列表 temperatures，对于每一天，需要至少多少天才能等到更高的温度。如果之后没有更高的温度，则输出 0。使用单调递减栈（栈底到栈顶递减），栈中存放索引。遍历温度，当当前温度高于栈顶索引对应的温度时，弹出栈顶并计算天数差。
1
2
3
4
5
6
7
8
9
10
11
def daily_temperatures(temperatures):
    n = len(temperatures)
    stack = []          # 栈中存放下标，且下标对应的温度保持递减
    res = [0] * n
    for i in range(n):
        # 当前温度比栈顶下标对应的温度高，说明找到了栈顶的下一个更高温度
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            res[idx] = i - idx
        stack.append(i)
    return res

下一个更大元素

  • 说明：给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。找出 nums1 中每个元素在 nums2 中的下一个比其大的元素。使用单调栈预先计算 nums2 中每个元素的下一个更大元素，存入哈希表，然后查询结果。
1
2
3
4
5
6
7
8
9
10
11
12
def next_greater_element(nums1, nums2):
    # 先计算 nums2 中每个元素的下一个更大元素，存入字典
    next_greater_map = {}
    stack = []          # 单调递减栈，存放索引
    for i in range(len(nums2)):
        while stack and nums2[i] > nums2[stack[-1]]:
            idx = stack.pop()
            next_greater_map[nums2[idx]] = nums2[i]
        stack.append(i)
    # 对于未找到更大元素的元素，字典中默认值为 -1
    res = [next_greater_map.get(num, -1) for num in nums1]
    return res

接雨水

  • 说明：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子下雨后能接多少雨水。使用单调递减栈，当遇到比栈顶高的柱子时，弹出栈顶作为底部，左边界为新的栈顶，右边界为当前柱子，计算当前凹槽的雨水量并累加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def trap(height):
    stack = []          # 单调递减栈，存储下标
    water = 0
    for i in range(len(height)):
        # 当前柱子高于栈顶柱子时，可能形成凹槽
        while stack and height[i] > height[stack[-1]]:
            bottom_idx = stack.pop()        # 弹出底部下标
            if not stack:                    # 左边界不存在，无法积水
                break
            left_idx = stack[-1]              # 左边界下标
            # 计算当前凹槽的雨水量
            h = min(height[left_idx], height[i]) - height[bottom_idx]
            w = i - left_idx - 1
            water += h * w
        stack.append(i)
    return water

表达式求值

  1. 说明：计算后缀表达式（逆波兰表达式）的值，或将中缀表达式转为后缀表达式（调度场算法）。栈用于保存操作数或运算符，根据运算规则进行压栈和弹栈。
  2. 题型：逆波兰表达式求值（力扣 150. 逆波兰表达式求值），中缀表达式（力扣 772. 基本计算器 III）

逆波兰表达式求值

  • 说明：根据逆波兰表示法，求表达式的值。有效运算符包括 +、-、*、/。每个操作数可以是整数或其他表达式。使用栈：遇到数字入栈，遇到运算符则弹出两个操作数计算后入栈。注意除法需向零截断（即 int(b / a) 或 int(b / a) 在 Python 中需特殊处理）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def eval_rpn(tokens):
    stack = []
    for token in tokens:
        if token in {"+", "-", "*", "/"}:
            # 注意弹出顺序：先弹出的是右操作数，后弹出的是左操作数
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:  # token == "/"
                # 向零截断：int(left / right) 在正负数时可能有问题，用 int(left / right) 或 left // right（需注意 Python 的 // 是向下取整）
                # 因此采用 int(left / right) 实现向零取整
                stack.append(int(left / right))
        else:
            stack.append(int(token))
    return stack[0]

基本计算器 III（力扣 772）

  • 说明：实现一个基本的计算器来计算简单的表达式字符串。表达式可以包含括号、加、减、乘、除，以及非负整数（可能有多位数）。使用双栈法：操作数栈 nums 和运算符栈 ops。遍历字符串，遇到数字时累加得到完整数字；遇到 ‘(‘ 直接入 ops；遇到 ‘)’ 则计算直到遇到 ‘(‘；遇到运算符时，先处理栈顶优先级不低于当前运算符的运算，再将当前运算符入栈。遍历结束后清空 ops。需注意处理负号（如 -2+1 或表达式开头为 -），可在遇到 - 时检查前一个字符是否为 ‘(‘ 或开头，若是则先在 nums 中补 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def calculate(s: str) -> int:
    def apply_operator(op, left, right):
        if op == '+':
            return left + right
        if op == '-':
            return left - right
        if op == '*':
            return left * right
        if op == '/':
            return int(left / right)  # 向零截断

    def precedence(op):
        if op in ('+', '-'):
            return 1
        if op in ('*', '/'):
            return 2
        return 0  # 其他字符（如 '('）优先级最低

    nums = []      # 操作数栈
    ops = []       # 运算符栈
    i = 0
    n = len(s)

    while i < n:
        ch = s[i]
        if ch == ' ':
            i += 1
            continue
        if ch.isdigit():
            # 读取完整数字
            num = 0
            while i < n and s[i].isdigit():
                num = num * 10 + int(s[i])
                i += 1
            nums.append(num)
            continue
        elif ch == '(':
            ops.append(ch)
        elif ch == ')':
            # 计算直到遇到 '('
            while ops and ops[-1] != '(':
                op = ops.pop()
                right = nums.pop()
                left = nums.pop()
                nums.append(apply_operator(op, left, right))
            ops.pop()  # 弹出 '('
        else:  # 运算符
            # 处理负号：若当前运算符是 '-' 且前面是 '(' 或位于表达式开头
            if ch == '-' and (i == 0 or s[i-1] == '('):
                nums.append(0)  # 补 0，将 -x 转为 0 - x
            # 处理栈内优先级不低于当前运算符的运算
            while ops and ops[-1] != '(' and precedence(ops[-1]) >= precedence(ch):
                op = ops.pop()
                right = nums.pop()
                left = nums.pop()
                nums.append(apply_operator(op, left, right))
            ops.append(ch)
        i += 1

    # 处理剩余运算符
    while ops:
        op = ops.pop()
        right = nums.pop()
        left = nums.pop()
        nums.append(apply_operator(op, left, right))

    return nums[0]

队列

操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import deque

# 创建队列
queue = deque()

# 入队
queue.append(x)

# 出队
x = queue.popleft()

# 查看队首
front = queue[0]

# 判空
if not queue:
    print("队列为空")

双端队列

  1. 说明：deque 支持两端高效插入和删除，可作为队列或栈使用。常用于需要两端操作的场景，如滑动窗口、回文检查、设计循环双端队列等。
  2. 题型：力扣 641. 设计循环双端队列，力扣 933. 最近的请求次数

循环双端队列

  • 思路：可以使用数组或双向链表实现，这里使用数组（列表）模拟循环队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class MyCircularDeque:
    def __init__(self, k: int):
        """
        初始化，队列容量为 k
        """
        self.capacity = k
        self.queue = [0] * k          # 固定大小数组
        self.front = 0                 # 队首指针
        self.rear = 0                   # 队尾指针，指向下一个插入位置
        self.size = 0                   # 当前元素个数

    def insertFront(self, value: int) -> bool:
        """头部插入，成功返回 True，否则返回 False"""
        if self.isFull():
            return False
        self.front = (self.front - 1) % self.capacity
        self.queue[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        """尾部插入，成功返回 True，否则返回 False"""
        if self.isFull():
            return False
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        """删除头部元素，成功返回 True，否则返回 False"""
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        """删除尾部元素，成功返回 True，否则返回 False"""
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1) % self.capacity
        self.size -= 1
        return True

    def getFront(self) -> int:
        """获取头部元素，若队列为空返回 -1"""
        if self.isEmpty():
            return -1
        return self.queue[self.front]

    def getRear(self) -> int:
        """获取尾部元素，若队列为空返回 -1"""
        if self.isEmpty():
            return -1
        # 尾部指针 rear 指向下一个插入位置，所以最后一个元素在 rear-1 处
        return self.queue[(self.rear - 1) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

最近的请求次数

  • 说明：用队列存储请求时间，每次调用时先将新时间入队，然后移除队首所有小于 t-3000 的时间，最后返回队列长度。
1
2
3
4
5
6
7
8
9
10
class RecentCounter:

    def __init__(self):
        self.times = deque()

    def ping(self, t: int) -> int:
        while self.times and self.times[0] < (t - 3000):
            self.times.popleft()
        self.times.append(t)
        return len(self.times)

优先队列（堆）

  1. 说明：需要动态维护集合的最值，并支持插入和删除最值。Python 的 heapq 模块实现最小堆，可通过取负数模拟最大堆。常用于 TopK 问题、合并有序链表、任务调度、Dijkstra 算法等。
  2. 题型：力扣 215. 数组中的第K个最大元素（用堆或快速排序），力扣 23. 合并K个升序链表（用堆维护每个链表的头节点），力扣 347. 前 K 个高频元素（用堆统计频率），力扣 295. 数据流的中位数（用两个堆维护），
函数 描述
heappush(heap, item) 将元素 item 压入堆中，并保持堆的不变性。
heappop(heap) 弹出并返回堆中的最小元素，同时保持堆的不变性。
heapify(x) 将列表 x 原地转换为一个合法的堆。

数组中的第K个最大元素

  • 说明：维护一个大小为 k 的最小堆，堆顶即为第 k 大的元素。
1
2
3
4
5
6
7
8
9
import heapq

def findKthLargest(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)       # 弹出最小的，保持堆大小为 k
    return heap[0]                     # 堆顶是第 k 大的

合并K个升序链表

  • 说明：合并 k 个升序链表，返回合并后的升序链表。使用最小堆，将每个链表的头节点（值和节点）存入堆，每次弹出最小节点，然后将该节点的下一个节点入堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    # 创建最小堆，元素为 (节点值, 节点索引, 节点)
    # 使用索引避免节点值相等时的比较问题
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node)) # 即先比较第一个元素 node.val，如果相等则比较第二个元素 i，如果还相等才比较第三个元素 node
    
    dummy = ListNode(0)
    cur = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

前 K 个高频元素

  • 说明：返回数组中出现频率前 k 高的元素。先用哈希表统计频率，然后维护一个大小为 k 的最小堆（按频率排序），最后堆中元素即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq
from collections import Counter

def topKFrequent(nums, k):
    # 统计频率
    freq = Counter(nums)
    # 使用最小堆，保存 (频率, 元素)
    heap = []
    for num, cnt in freq.items():
        heapq.heappush(heap, (cnt, num))
        if len(heap) > k:
            heapq.heappop(heap)
    # 取出堆中元素
    return [num for cnt, num in heap]

数据流的中位数

  • 说明：设计一个数据结构，支持添加整数并返回当前所有元素的中位数。使用两个堆：一个大顶堆（存较小的一半）和一个小顶堆（存较大的一半）。保持两个堆大小平衡，即可随时获取中位数。

单调队列

  1. 说明：维护一个队列，使其元素保持单调递增或递减，常用于解决滑动窗口最值问题。单调队列的核心思想是在入队时删除破坏单调性的元素，从而保证队首始终是当前窗口的最值。与单调栈类似，但这里是队列结构（先进先出）。
  2. 题型：力扣 239. 滑动窗口最大值，力扣 1438. 绝对差不超过限制的最长连续子数组

滑动窗口最大值

  • 说明：给定数组 nums 和滑动窗口大小 k，返回每个窗口中的最大值。使用双端队列存储元素下标，保持队列中下标对应的值单调递减（队首最大）。每次移动窗口时，移除队首不在窗口内的下标，并保持单调性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()
        res = []
        left = 0
        for right in range(len(nums)):
            while dq and nums[dq[-1]] < nums[right]:
                dq.pop()
            dq.append(right)
            while right - left + 1 > k:
                if dq[0] == left:
                    dq.popleft()
                left += 1
            if right - left + 1 == k:
                res.append(nums[dq[0]])
        return res

绝对差不超过限制的最长连续子数组

  • 说明：给定数组 nums 和限制 limit，求最长连续子数组的长度，使得子数组中任意两个元素的绝对差 ≤ limit。使用两个单调队列（一个维护最大值，一个维护最小值），滑动窗口扩张右边界时更新队列，当窗口内最大值与最小值差超过 limit 时收缩左边界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        min_dq = deque()
        max_dq = deque()
        left = 0
        res = 0
        for right in range(len(nums)):
            while min_dq and nums[min_dq[-1]] > nums[right]:
                min_dq.pop()
            while max_dq and nums[max_dq[-1]] < nums[right]:
                max_dq.pop()
            min_dq.append(right)
            max_dq.append(right)
            while nums[max_dq[0]] - nums[min_dq[0]] > limit:
                if max_dq[0] == left:
                    max_dq.popleft()
                if min_dq[0] == left:
                    min_dq.popleft()
                left += 1
            res = max(right - left + 1, res)
        return res

哈希表

定义

  • 哈希表（字典）是一种键值对存储结构，通过哈希函数将键映射到存储位置，实现 O(1) 平均时间复杂度的插入、删除和查找。
  • Python 中 dict 和 set 分别实现哈希表和哈希集合。
  • 适用场景：需要快速判断元素是否存在、统计频率、建立映射关系、去重等。

哈希表注意事项

  • 哈希函数冲突：Python 字典已内置处理，一般无需关心。
  • 键的类型必须可哈希（不可变类型），如 int、str、tuple。若需使用列表等作为键，可转为元组。
  • 使用 defaultdict 或 Counter 可以简化计数代码。

两数之和类（查找表优化）

  1. 说明：遍历数组时，将已经访问过的元素及其下标存入哈希表。对于当前元素 nums[i]，检查 target - nums[i] 是否在哈希表中，若存在则找到答案。这种“空间换时间”的思想将暴力 O(n²) 降为 O(n)。
  2. 题型：力扣 1. 两数之和，力扣，力扣 15. 三数之和（哈希辅助去重）

两数之和

  • 说明：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。假设每种输入只对应一个答案，且不能重复使用同一个元素。
1
2
3
4
5
6
7
8
9
def two_sum(nums: List[int], target: int) -> List[int]:
    mapping = {}                     # 值 -> 下标
    for i in range(len(nums)):
        num = nums[i]
        complement = target - num
        if complement in mapping:
            return [mapping[complement], i]
        mapping[num] = i
    return []

三数之和

  • 说明：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0。找出所有不重复的三元组。哈希表可用于去重和查找，但主流解法是排序+双指针。这里展示哈希辅助去重的思路（需先排序，并注意跳过重复元素）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def twoSum(self, nums, target):
        mapping = set()
        res = []
        for i in range(len(nums)):
            if target - nums[i] in mapping:
                res.append([target - nums[i], nums[i]])
            mapping.add(nums[i])
        return res

    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res = []
        mapping = set()
        for i in range(len(nums)-1):
            if nums[i] in mapping:               # skip duplicate first numbers
                continue
            target1 = - nums[i]
            res1 = [nums[i]]
            res2_list = self.twoSum(nums[i+1:], target1)
            for res2 in res2_list:
                res3 = res1+res2
                if res3 not in res:
                    res.append(res3)
            mapping.add(nums[i])
        return res

计数统计

  1. 说明：利用哈希表统计元素出现的次数（频率），是解决“出现次数”相关问题的核心方法。例如判断两个字符串是否为字母异位词、求数组中出现次数最多的元素等。
  2. 题型：力扣 242. 有效的字母异位词，力扣 169. 多数元素，力扣 383. 赎金信，力扣 387. 字符串中的第一个唯一字符

有效的字母异位词

  • 说明：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。即两个字符串中字符出现的种类和次数均相同。
1
2
3
4
5
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        freq1 = Counter(s)
        freq2 = Counter(t)
        return freq1 == freq2

多数元素

  • 说明：给定一个大小为 n 的数组，找到其中的多数元素，即出现次数大于 ⌊ n/2 ⌋ 的元素。可以假设数组非空，且多数元素一定存在。使用哈希表统计频率，遍历找出次数最大的。
1
2
3
4
5
6
7
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        freq = Counter(nums)
        n = len(nums)
        for key, val in freq.items():
            if val > n // 2:
                    return key

赎金信

  • 说明：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true；否则返回 false。magazine 中的每个字符只能在 ransom 中使用一次。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        frqe1 = Counter(ransomNote)
        frqe2 = Counter(magazine)
        for key, val in frqe1.items():
            if key in frqe2 and frqe2[key] >= val:
                pass
            else:
                return False
        return True

字符串中的第一个唯一字符

  • 说明：给定一个字符串数组，将字母异位词组合在一起。可以按排序后的字符串作为键。
1
2
3
4
5
6
7
class Solution:
    def firstUniqChar(self, s: str) -> int:
        freq = Counter(s)
        for i in range(len(s)):
            if freq[s[i]] == 1:
                return i
        return -1

分组归类

  1. 说明：将具有某种共同特征的元素归为一类，常用哈希表将“特征”映射到对应列表。例如字母异位词分组，特征可以是排序后的字符串，也可以是字符计数的元组。
  2. 题型：力扣 49. 字母异位词分组，力扣 249. 移位字符串分组，力扣 336. 回文对

字母异位词分组

  • 说明：给定一个字符串数组，将字母异位词组合在一起。可以按排序后的字符串作为键。
1
2
3
4
5
6
7
8
9
10
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mapping = {}
        for s in strs:
            key = ''.join(sorted(s))
            if key in mapping:
                mapping[key].append(s)
            else:
                mapping[key] = [s]
        return list(mapping.values())

移位字符串分组

  • 说明：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def group_strings(strings: List[str]) -> List[List[str]]:
    mapping = {}
    for i in range(len(strings)):
        s = strings[i]
        # 计算移位特征：将每个字符相对于第一个字符的偏移量归一化
        key = []
        for j in range(len(s)):
            ch = s[j]
            offset = (ord(ch) - ord(s[0])) % 26
            key.append(offset)
        key = tuple(key)   # 列表不可哈希，转为元组
        if key not in mapping:
            mapping[key] = []
        mapping[key].append(s)
    return list(mapping.values())

回文对

  • 说明：对于每个单词 word，我们尝试将它拆分成前缀 prefix 和后缀 suffix，检查两种可能形成回文的情况：
    • 前缀是回文：如果 prefix 本身是回文，那么只需要 suffix 的逆序字符串存在于单词列表中，且不是当前单词本身，就可以将那个单词放在前面，当前单词放在后面，拼接成回文。
    • 后缀是回文：如果 suffix 本身是回文，那么只需要 prefix 的逆序字符串存在于单词列表中，且不是当前单词本身，就可以将当前单词放在前面，那个单词放在后面，拼接成回文。

为了快速查找逆序字符串，我们预先将所有单词及其下标存入哈希表 mapping。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def palindrome_pairs(words: List[str]) -> List[List[int]]:
    # 建立单词到下标的映射
    mapping = {word: i for i in range(len(words)) for word in [words[i]]}
    res = []
    for i in range(len(words)):
        word = words[i]
        n = len(word)
        # 枚举所有可能的前后缀分界点 j
        for j in range(n + 1):
            prefix = word[:j]
            suffix = word[j:]
            # 情况1：前缀是回文 → 需要后缀的逆序存在
            if prefix == prefix[::-1]:
                rev_suffix = suffix[::-1]
                if rev_suffix in mapping and mapping[rev_suffix] != i:
                    res.append([mapping[rev_suffix], i])  # 逆序单词在前，当前在后
            # 情况2：后缀是回文 → 需要前缀的逆序存在（且 j != n 避免重复空后缀）
            if j != n and suffix == suffix[::-1]:
                rev_prefix = prefix[::-1]
                if rev_prefix in mapping and mapping[rev_prefix] != i:
                    res.append([i, mapping[rev_prefix]])  # 当前在前，逆序单词在后
    return res

集合与连续性

  1. 说明：利用哈希集合（set）存储元素，可以快速判断一个数是否存在。对于最长连续序列问题，通过集合去重后，只从连续段的起点开始向后枚举，避免重复计算，达到 O(n) 时间复杂度。
  2. 题型：力扣 128. 最长连续序列

最长连续序列

  • 说明：
1
2
3
4
5
6
7
8
9
10
11
12
13
def longest_consecutive(nums: List[int]) -> int:
    mapping = set(nums)  # 使用集合存储所有数
    longest = 0
    for num in mapping:  # 遍历集合中的数（已去重）
        # 只有当 num-1 不在集合中时，才作为连续序列的起点
        if num - 1 not in mapping:
            current = num
            length = 1
            while current + 1 in mapping:
                current += 1
                length += 1
            longest = max(longest, length)
    return longest

映射关系

  1. 说明：哈希表可以建立一对一的映射关系，常用于判断两个结构是否同构、模式匹配等。例如同构字符串中，需要建立字符到字符的双向映射，避免出现多对一的情况。
  2. 题型：力扣 205. 同构字符串，力扣 290. 单词规律，力扣 953. 验证外星语词典

同构字符串

  • 说明：给定两个字符串 s 和 t，判断它们是否是同构的。即 s 中的字符可以映射到 t 中的字符，且映射是双射（一一对应）。
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        mapping_st, mapping_ts = {}, {}
        for i in range(len(s)):
            cs = s[i]
            ct = t[i]
            if (cs in mapping_st and mapping_st[cs] != ct) or (ct in mapping_ts and mapping_ts[ct] != cs):
                return False
            mapping_st[cs] = ct
            mapping_ts[ct] = cs
        return True

树

图

字符串

查找

适用情况

  1. 数据具有有序性
  2. 问题可以转化为判定问题，且判定结果在某个分界点前后呈现“是/否”的单调变化
  3. 答案在一个明确的范围内，且可以快速验证

复杂度

  • 时间复杂度： O(log n)
  • 空间复杂度： O(1)

模版

1
2
3
4
5
6
7
8
9
10
11
def half_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:                  # 闭区间 [left, right]
        mid = left + (right - left) // 2   # 防止溢出
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1                 # target 在右半部分
        else:
            right = mid - 1                 # target 在左半部分
    return -1                              # 未找到

变种

查找左右边界

  1. 说明：数组有序但可能包含重复元素，需要找到目标值的第一个出现位置和最后一个出现位置。核心是改变 nums[mid] == target 时的处理逻辑：
    • 找左边界：当相等时，不立即返回，而是继续向左收缩（right = mid - 1），最后退出时 left 指向第一个 ≥ target 的位置。
    • 找右边界：当相等时，继续向右收缩（left = mid + 1），最后退出时 right 指向最后一个 ≤ target 的位置。
  2. 题型：查找左右边界（力扣 34. 在排序数组中查找元素的第一个和最后一个位置）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def search_range(nums, target):
    def find_left():
        # 找第一个 >= target 的位置（即左边界）
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:  # nums[mid] >= target，继续向左
                right = mid - 1
        return left  # left 是第一个 >= target 的下标

    def find_right():
        # 找最后一个 <= target 的位置（即右边界）
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:  # nums[mid] > target，继续向右
                right = mid - 1
        return right  # right 是最后一个 <= target 的下标

    left_idx = find_left()
    # 检查 left_idx 是否越界且等于 target
    if left_idx >= len(nums) or nums[left_idx] != target:
        return [-1, -1]
    right_idx = find_right()
    return [left_idx, right_idx]

寻找峰值

  1. 说明：数组不一定有序，但相邻元素不等。峰值是指大于相邻左右的元素（可认为 nums[-1] = nums[n] = -∞）。通过比较 mid 和 mid+1 的值，决定往哪一侧收缩：
    • 如果 nums[mid] > nums[mid+1]，说明峰值在左侧（包括 mid），移动右指针。
    • 否则峰值在右侧（mid+1 更大），移动左指针。
  2. 题型：寻找峰值（力扣 162. 寻找峰值）
1
2
3
4
5
6
7
8
9
10
11
def find_peak_element(nums):
    left, right = 0, len(nums) - 1
    while left < right:  # 注意是 left < right，最终 left == right 时即为峰值
        mid = left + (right - left) // 2
        if nums[mid] > nums[mid + 1]:
            # 峰值在左侧（包含 mid）
            right = mid
        else:
            # 峰值在右侧（mid+1 更大）
            left = mid + 1
    return left  # 或 right，此时 left == right

搜索旋转排序数组

  1. 说明：在旋转后的有序数组（无重复）中搜索目标值。数组原本是升序的，但在某个未知点进行了旋转，例如 [4,5,6,7,0,1,2]。核心思路是每次二分后，先判断哪一部分是有序的，然后根据目标值是否在有序区间内决定搜索方向。
  2. 题型：搜索旋转排序数组(力扣 33. 搜索旋转排序数组)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # 判断左半部分 [left, mid] 是否有序
        if nums[left] <= nums[mid]:          # 左半有序
            # 如果目标值在左半部分范围内
            if nums[left] <= target < nums[mid]:
                right = mid - 1               # 在左半部分继续搜索
            else:
                left = mid + 1                 # 在右半部分搜索
        else:                                 # 右半有序（即左半无序，右半必然有序）
            # 如果目标值在右半部分范围内
            if nums[mid] < target <= nums[right]:
                left = mid + 1                 # 在右半部分搜索
            else:
                right = mid - 1                 # 在左半部分搜索
    return -1

搜索旋转排序数组 II(力扣 81. 搜索旋转排序数组II)

  1. 说明：与 33 题类似，但数组中存在重复元素。当 nums[left] == nums[mid] 时无法判断哪边有序，需要收缩左边界去重。
  2. 题型：搜索旋转排序数组 II(力扣 81. 搜索旋转排序数组II)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def search_rotated_ii(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return True

        # 关键处理：当左边界与中间值相等时，无法判断有序性，左边界右移一位
        if nums[left] == nums[mid]:
            left += 1
            continue

        # 以下逻辑与无重复版本类似
        if nums[left] <= nums[mid]:          # 左半部分有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                                 # 右半部分有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return False

排序

冒泡排序

  • 说明：重复遍历数组，比较相邻元素，若顺序错误则交换，直到没有需要交换的元素。每轮将最大元素“冒泡”到末尾。适用于小规模数据。
  • 时间复杂度：O(n²)（平均和最坏），O(n)（最好，已有序）
  • 空间复杂度：O(1)
  • 稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
def bubble_sort(arr):
    n = len(arr)
    # 外层循环控制排序的趟数，n个元素需要n-1趟冒泡
    for i in range(n-1):
        swapped = False                     # 标记本轮是否发生交换，用于提前结束
        # 内层循环控制每趟比较的范围：每完成一趟，末尾已确定一个最大值，所以范围缩小
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:            # 如果前一个大于后一个，交换
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True               # 发生了交换
        if not swapped:                       # 没有交换说明已经有序，提前退出
            break
    return arr

选择排序

  • 说明：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。简单直观，但不论数据如何，比较次数固定。
  • 时间复杂度：O(n²)（所有情况）
  • 空间复杂度：O(1)
  • 稳定性：不稳定
1
2
3
4
5
6
7
8
9
def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):                     # 依次确定每个位置
        min_idx = i                           # 假设当前位置为最小值索引
        for j in range(i+1, n):               # 在未排序部分找更小的
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # 将最小值放到位置 i
    return arr

插入排序

  • 说明：将数组分为已排序和未排序两部分，每次将未排序的第一个元素插入到已排序部分的正确位置。适合小规模或基本有序的数据。
  • 时间复杂度：O(n²)（平均和最坏），O(n)（最好，已有序）
  • 空间复杂度：O(1)
  • 稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):             # 从第二个元素开始，依次插入
        key = arr[i]                          # 当前待插入的元素
        j = i - 1                              # 已排序部分的最后一个索引
        # 将比 key 大的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key                         # 将 key 插入正确位置
    return arr

希尔排序

  • 说明：插入排序的改进版，通过将数组按一定间隔分组进行插入排序，逐步缩小间隔，最后间隔为1时进行一次完整插入排序。间隔序列常取 gap = gap//2。
  • 时间复杂度：取决于间隔序列，平均约 O(n^1.3)，最坏 O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shell_sort(arr):
    n = len(arr)
    gap = n // 2                              # 初始间隔
    while gap > 0:
        # 对每个分组进行插入排序，每组元素间隔为 gap
        for i in range(gap, n):                # i 指向每个分组的第二个元素
            key = arr[i]                        # 当前待插入的元素
            j = i - gap                          # 指向组内前一个元素
            # 在组内进行插入排序，将比 key 大的元素向后移动 gap 位
            while j >= 0 and arr[j] > key:
                arr[j + gap] = arr[j]            # 后移
                j -= gap
            arr[j + gap] = key                    # 插入正确位置
        gap //= 2                               # 缩小间隔
    return arr

归并排序

  • 说明：采用分治法，将数组分成两半分别排序，然后合并两个有序数组。递归实现，需要额外空间。
  • 时间复杂度：O(n log n)（所有情况）
  • 空间复杂度：O(n)
  • 稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(arr):
    n = len(arr)
    if n <= 1:                          # 递归终止条件
        return arr
    mid = n // 2                         # 中间位置
    left_arr = merge_sort(arr[:mid])                # 递归排序左半
    right_arr = merge_sort(arr[mid:])               # 递归排序右半
    return merge(left_arr, right_arr)                   # 合并两个有序数组

def merge(left_arr, right_arr):w
    result = []
    i = j = 0
    # 比较两个数组的元素，按顺序放入 result
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    # 将剩余部分加入 result
    result.extend(left_arr[i:])
    result.extend(right_arr[j:])
    return result

快速排序

  • 说明：分治法，选择一个基准（pivot），将小于基准的放左边，大于基准的放右边，然后递归排序左右子数组。平均性能最好，但最坏情况（已有序且选最左为基准）退化为 O(n²)。
  • 时间复杂度：平均 O(n log n)，最坏 O(n²)
  • 空间复杂度：O(log n)（递归栈）
  • 稳定性：不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(arr, left, right):
    if left >= right:                          # 递归终止条件
        return arr
    pivot = partition(arr, left, right)        # 获取基准位置
    quick_sort(arr, left, pivot - 1)           # 递归排序左半
    quick_sort(arr, pivot + 1, right)          # 递归排序右半
    return arr

def partition(arr, left, right):
    # 以 arr[right] 为基准
    i = left                                    # i 指向下一个待放置的位置（即小于等于基准的区域的右边界）
    for j in range(left, right):
        if arr[j] <= arr[right]:                 # 如果当前元素 <= 基准
            arr[i], arr[j] = arr[j], arr[i]      # 将其交换到左边区域
            i += 1                                # 扩大左边区域
    # 将基准放到正确位置（i 处），此时左边都 <= 基准，右边都 > 基准
    arr[i], arr[right] = arr[right], arr[i]
    return i

数组中的第K个最大元素

  1. 说明：调用 partition 将数组分为两部分，左侧元素 ≤ 基准，右侧元素 > 基准。若基准位置 pivot 恰好等于目标索引 target，则直接返回该元素；若 pivot < target，说明目标在右侧，移动左边界；否则目标在左侧，移动右边界。
  2. 题型：数组中的第K个最大元素（力扣 215. 数组中的第K个最大元素）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def find_kth_largest(nums, k):
    # 将第k大转换为第 (n-k) 小（0-based索引）
    target = len(nums) - k
    left, right = 0, len(nums) - 1

    while left <= right:
        pivot = partition(nums, left, right)   # 获取基准最终位置
        if pivot == target:
            return nums[pivot]
        elif pivot < target:
            left = pivot + 1                    # 在右侧继续查找
        else:
            right = pivot - 1                   # 在左侧继续查找
    return -1                                    # 理论上不会执行到这里

def partition(arr, left, right):
    i = left                                     # i 指向下一个待放置的位置（即 <= 基准的区域边界）
    for j in range(left, right):
        if arr[j] <= arr[right]:                  # 当前元素 <= 基准，交换到左侧
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    # 将基准放到正确位置（i 处）
    arr[i], arr[right] = arr[right], arr[i]
    return i

堆排序

  • 说明：利用堆（优先队列）进行排序。先将数组构建成最大堆，然后反复将堆顶（最大值）与末尾交换，并调整堆。原地排序。
  • 时间复杂度：O(n log n)（所有情况）
  • 空间复杂度：O(1)
  • 稳定性：不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def heap_sort(arr):
    n = len(arr)
    # 构建最大堆：从最后一个非叶子节点开始向下调整
    for i in range(n//2-1, -1, -1):
        heapify(arr, n, i)
    # 逐个取出堆顶（最大值）放到数组末尾
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]        # 交换堆顶与末尾
        heapify(arr, i, 0)                      # 调整剩余部分为堆
    return arr

def heapify(arr, n, i):
    max_idx = i                                 # 假设当前节点最大
    left = 2*i + 1
    right = 2*i + 2
    # 如果左子节点存在且大于当前最大，更新 max_idx
    if left < n and arr[left] > arr[max_idx]:
        max_idx = left
    # 如果右子节点存在且大于当前最大，更新 max_idx
    if right < n and arr[right] > arr[max_idx]:
        max_idx = right
    if max_idx != i:                            # 如果最大值不是当前节点
        arr[i], arr[max_idx] = arr[max_idx], arr[i]  # 交换
        heapify(arr, n, max_idx)                 # 递归调整子树
    return arr

计数排序

  • 说明：非比较排序，适用于数据范围不大的整数。统计每个值出现的次数，然后按顺序输出。要求输入数据是非负整数。
  • 时间复杂度：O(n + k)，k 为数据范围
  • 空间复杂度：O(k)
  • 稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def counting_sort(arr):
    n = len(arr)
    if n <= 1:                          # 递归终止条件
        return arr
    max_val = max(arr)                          # 找到最大值确定计数数组大小
    count = [0] * (max_val + 1)                  # 初始化计数数组
    for num in arr:                              # 统计每个元素出现次数
        count[num] += 1
    # 累加计数，使得 count[i] 表示小于等于 i 的元素个数
    for i in range(1, len(count)):
        count[i] += count[i-1]
    output = [0] * n                      # 输出数组
    # 从后往前遍历原数组，保证稳定性（相同元素相对顺序不变）
    for num in reversed(arr):
        output[count[num]-1] = num
        count[num] -= 1
    arr[:] = output[:]
    return arr

桶排序

  • 说明：将数据分到有限数量的桶里，每个桶内分别排序（可使用其他排序），然后合并。适用于数据均匀分布的情况。
  • 时间复杂度：平均 O(n + n²/k + k)（取决于桶内排序），最坏 O(n²)
  • 空间复杂度：O(n + k)
  • 稳定性：取决于桶内排序算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def bucket_sort(arr, bucket_size=5):
    n = len(arr)
    if n <= 1:                          # 递归终止条件
        return arr
    min_val, max_val = min(arr), max(arr)
    # 计算桶的数量，每个桶的范围为 bucket_size
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets = [[r for _ in range(bucket_count)]   # 创建空桶
    for num in arr:
        # 确定当前元素属于哪个桶
        idx = (num - min_val) // bucket_size
        buckets[idx].append(num)
    output = []
    for bucket in buckets:
        if bucket:
            # 桶内使用插入排序（或其他稳定排序）
            insertion_sort(bucket)
            output.extend(bucket)
    arr[:] = output[:]
    return arr

基数排序

  • 说明：非比较排序，按低位到高位依次进行计数排序（或桶排序）。适用于整数或定长字符串。
  • 时间复杂度：O(d * (n + k))，d 为位数，k 为基数（如10）
  • 空间复杂度：O(n + k)
  • 稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def radix_sort(arr):
    n = len(arr)
    if n <= 1:                          # 递归终止条件
        return arr
    max_val = max(arr)                           # 找到最大值确定最高位数
    exp = 1                                       # 当前位数（个位、十位...）
    while max_val // exp > 0:                     # 直到最高位处理完
        counting_sort_by_digit(arr, exp)          # 按当前位进行计数排序
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    count = [0] * 10                              # 0-9 共10个数字
    # 统计当前位每个数字的出现次数
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
    # 累加计数，使得 count[i] 表示当前位 <= i 的元素个数
    for i in range(1, 10):
        count[i] += count[i-1]
    output = [0] * n
    # 从后往前遍历原数组，保证稳定性
    for num in reversed(arr):
        digit = (num // exp) % 10
        output[count[digit]-1] = num
        count[digit] -= 1
    # 将排序结果复制回原数组
    arr[:] = output[:]
    return arr

排序总结

排序算法 最好时间复杂度 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性 适用条件
冒泡排序 O(n) O(n²) O(n²) O(1) 稳定 1. 适用于小规模数据
2. 对稳定性有要求的场景
选择排序 O(n²) O(n²) O(n²) O(1) 不稳定 1. 适用于小规模数据
2. 对空间限制严格（原地排序）
3. 不要求稳定性
插入排序 O(n) O(n²) O(n²) O(1) 稳定 1. 适用于小规模或基本有序的数据
2. 数据基本有序时效率高
希尔排序 O(n log n) O(n^1.3) O(n²) O(1) 不稳定 1. 适用于中等规模数据
2. 对稳定性无要求
3. 需要原地排序
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定 1. 适用于大规模数据
2. 需要稳定排序
3. 允许 O(n) 额外空间
快速排序 O(n log n) O(n log n) O(n²) O(log n) 不稳定 1. 适用于大规模数据
2. 平均性能最优
3. 对最坏情况不敏感（可优化）
堆排序 O(n log n) O(n log n) O(n log n) O(1) 不稳定 1. 适用于大规模数据
2. 需要原地排序
3. 对稳定性无要求
4. 常数时间要求不高
计数排序 O(n + k) O(n + k) O(n + k) O(n + k) 稳定 1. 输入为非负整数
2. 数据范围（k）较小，否则空间消耗大
3. 需要稳定排序
桶排序 O(n + k) O(n + k) O(n²) O(n + k) 稳定 1. 数据均匀分布
2. 数据范围已知且适合分桶
3. 可结合其他排序进行桶内排序
基数排序 O(d·(n + k)) O(d·(n + k)) O(d·(n + k)) O(n + k) 稳定 1. 适用于整数或定长字符串
2. 数据位数（d）较小
3. 需要稳定排序

位运算

回溯

动态规划

贪心算法