Skip to main content

Python 数据结构与算法

Python 提供了多种数据结构和算法，其中 collections 模块提供了一些高效的数据结构，而时间复杂度分析（Big O 记法）可以帮助我们衡量算法的效率。此外，常见的算法包括 排序、搜索、动态规划，它们在编程中广泛使用。

1️⃣ collections 模块​

Python 的 collections 模块提供了许多高级数据结构，包括 Counter（计数器）、deque（双端队列）和 defaultdict（带默认值的字典），它们可以优化代码性能。

(1) Counter - 计数器​

Counter 是 collections 模块中的一个子类，用于统计可迭代对象中元素的出现次数。

示例​

from collections import Counter

# 统计字符出现次数
text = "hello world"
counter = Counter(text)
print(counter)  # 输出：Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

# 统计单词出现次数
words = ["apple", "banana", "apple", "orange", "banana", "apple"]
word_count = Counter(words)
print(word_count)  # 输出：Counter({'apple': 3, 'banana': 2, 'orange': 1})

# 获取最常见的两个元素
print(word_count.most_common(2))  # 输出：[('apple', 3), ('banana', 2)]

(2) deque - 双端队列​

deque（double-ended queue）是一个双端队列，支持 O(1) 复杂度 的快速插入和删除操作，比 Python 内置的 list 更高效。

示例​

from collections import deque

# 初始化 deque
dq = deque(["a", "b", "c"])

# 在两端插入元素
dq.append("d")    # 末尾插入
dq.appendleft("z") # 头部插入
print(dq)  # 输出：deque(['z', 'a', 'b', 'c', 'd'])

# 在两端删除元素
dq.pop()  # 删除末尾
dq.popleft()  # 删除头部
print(dq)  # 输出：deque(['a', 'b', 'c'])

# 旋转队列
dq.rotate(1)  # 向右旋转 1 步
print(dq)  # 输出：deque(['c', 'a', 'b'])

(3) defaultdict - 带默认值的字典​

defaultdict 允许你在访问字典中 不存在的键时 自动初始化一个默认值，而不会抛出 KeyError。

示例​

from collections import defaultdict

# 创建一个默认值为 list 的字典
d = defaultdict(list)

# 向字典中添加值
d["fruits"].append("apple")
d["fruits"].append("banana")
d["vegetables"].append("carrot")

print(d)  
# 输出：defaultdict(<class 'list'>, {'fruits': ['apple', 'banana'], 'vegetables': ['carrot']})

# 访问不存在的键，不会报错，而是返回空列表
print(d["unknown"])  # 输出：[]

补充：namedtuple() 和 OrderedDict​

collections 模块中还有两个重要的数据结构：

  • namedtuple()（具名元组）：类似 tuple，但可以使用属性访问，提高可读性。
  • OrderedDict（有序字典）：在 Python 3.6+ 版本中，普通 dict 已经保持插入顺序，但 OrderedDict 仍然提供额外的功能，如 move_to_end()。

(4) namedtuple() - 具名元组​

namedtuple() 是 collections 提供的一种工厂方法，用于创建一个不可变的对象，类似于 tuple，但可以使用属性访问字段，而不仅仅是索引。

特点​

✅ 结构清晰，适用于轻量级数据存储
✅ 可通过索引或字段名访问
✅ 继承 tuple，不可变（Immutable）

示例 1：创建 namedtuple​

from collections import namedtuple

# 定义 namedtuple
Point = namedtuple('Point', ['x', 'y'])

# 创建实例
p = Point(3, 4)

# 访问属性
print(p.x, p.y)  # 输出: 3 4

# 也可以用索引访问
print(p[0], p[1])  # 输出: 3 4

# namedtuple 是不可变的
# p.x = 10  # 运行会报错

示例 2：提高代码可读性​

使用 namedtuple 代替 tuple，使代码更易理解。

# 用 tuple 存储员工信息（不推荐）
employee = ('Alice', 'Developer', 80000)

# 用 namedtuple 存储（推荐）
Employee = namedtuple('Employee', ['name', 'role', 'salary'])
alice = Employee(name='Alice', role='Developer', salary=80000)

print(alice.name, alice.role, alice.salary)
# 输出: Alice Developer 80000

示例 3：字典转换为 namedtuple​

data = {'x': 10, 'y': 20}
Point = namedtuple('Point', data.keys())
p = Point(**data)
print(p)  # 输出: Point(x=10, y=20)

(5) OrderedDict - 有序字典​

OrderedDict 是 collections 提供的有序字典，它会记住插入的顺序（Python 3.6+ 的 dict 也默认有序）。

特点​

✅ 维护插入顺序（Python 3.6+ 的 dict 也支持）
✅ 提供 move_to_end() 方法，便于调整顺序
✅ 适用于需要保持元素顺序的场景

示例 1：基本用法​

from collections import OrderedDict

# 创建 OrderedDict
ordered_dict = OrderedDict()
ordered_dict['a'] = 1
ordered_dict['b'] = 2
ordered_dict['c'] = 3

print(ordered_dict)  # 输出: OrderedDict([('a', 1), ('b', 2), ('c', 3)])

示例 2：与普通 dict 的区别​

# 普通字典（Python 3.6+ 默认有序）
dict1 = {'a': 1, 'b': 2, 'c': 3}

# OrderedDict 也是有序的
ordered_dict = OrderedDict({'a': 1, 'b': 2, 'c': 3})

print(dict1 == ordered_dict)  # True（Python 3.6+）

示例 3：move_to_end() 方法​

可以将某个键移动到末尾（或开头）。

ordered_dict.move_to_end('a')  # 把 'a' 移到末尾
print(ordered_dict)  # OrderedDict([('b', 2), ('c', 3), ('a', 1)])

ordered_dict.move_to_end('c', last=False)  # 把 'c' 移到开头
print(ordered_dict)  # OrderedDict([('c', 3), ('b', 2), ('a', 1)])

示例 4：排序 OrderedDict​

# 按照值排序
sorted_dict = OrderedDict(sorted(ordered_dict.items(), key=lambda x: x[1]))
print(sorted_dict)  # 输出: OrderedDict([('a', 1), ('b', 2), ('c', 3)])

2️⃣ 时间复杂度（Big O 记法）​

时间复杂度（Time Complexity）描述了 算法执行时间的增长趋势，通常用 Big O 记法 表示。

常见时间复杂度​

复杂度名称例子
O(1)常数时间访问数组元素
O(log n)对数时间二分查找
O(n)线性时间遍历列表
O(n log n)线性对数时间快速排序、归并排序
O(n²)二次时间冒泡排序、选择排序
O(2ⁿ)指数时间斐波那契递归
O(n!)阶乘时间旅行商问题

示例​

# O(1) - 常数时间
def constant_time(arr):
    return arr[0]  # 直接访问元素

# O(n) - 线性时间
def linear_time(arr):
    for item in arr:
        print(item)

# O(n^2) - 二次时间
def quadratic_time(arr):
    for i in arr:
        for j in arr:
            print(i, j)

3️⃣ 常见算法​

(1) 排序算法​

冒泡排序（O(n²))​

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([3, 1, 4, 1, 5, 9, 2]))

快速排序（O(n log n))​

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([3, 1, 4, 1, 5, 9, 2]))

(2) 搜索算法​

二分查找（O(log n))​

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search([1, 2, 3, 4, 5, 6], 4))  # 输出: 3

(3) 动态规划​

动态规划（Dynamic Programming, DP）适用于最优子结构问题，如 斐波那契数列、背包问题、最长公共子序列。

斐波那契数列（O(n)）​

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(10))  # 输出: 55

0-1 背包问题​

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
    
    return dp[n][W]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # 输出: 7

总结​

  • collections 模块提供了高效的数据结构，如 Counter、deque、defaultdict。
  • Big O 记法用于分析算法效率，常见时间复杂度包括 O(1)、O(n)、O(n log n)、O(n²)。
  • 重要算法：
    • 排序（冒泡、快速排序）
    • 搜索（二分查找）
    • 动态规划（斐波那契、背包问题）

这些知识对 数据结构与算法面试 非常重要，建议多加练习！🚀