Python 数据结构与算法

Python 内置数据结构

列表（List）

python复制
# 列表是动态数组，支持 append, extend, insert, remove, pop 等操作
lst = [1, 2, 3, 4, 5]

# append: O(1)
lst.append(6)

# insert: O(n)
lst.insert(0, 0)

# remove: O(n)，删除第一个匹配的元素
lst.remove(3)

# pop: O(1)，从末尾删除
lst.pop()

# 列表切片: O(k)，k 为切片长度
sub = lst[1:3]

字典（Dict）

python复制
# 字典基于哈希表实现
d = {'a': 1, 'b': 2}

# 查找、插入、删除: O(1) 平均
d['c'] = 3
print(d['a'])

# get 操作: O(1)
print(d.get('d', 'default'))  # 不存在返回 default

集合（Set）

python复制
# 集合基于哈希表，只存储 key
s = {1, 2, 3, 4, 5}

# 添加: O(1)
s.add(6)

# 查找: O(1)
print(3 in s)  # True

# 集合运算
s1 = {1, 2, 3}
s2 = {2, 3, 4}
print(s1 & s2)  # 交集: {2, 3}
print(s1 | s2)  # 并集: {1, 2, 3, 4}
print(s1 - s2)  # 差集: {1}

复杂度总结

常用算法技巧

双指针技巧

python复制
# 两数之和（有序数组）
def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current = numbers[left] + numbers[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

# 链表反转
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_linked_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

滑动窗口

python复制
# 无重复字符的最长子串
def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

二分查找

python复制
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 二分查找变体：查找左边界
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

常见排序算法

快速排序

python复制
def quicksort(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 quicksort(left) + middle + quicksort(right)

# 原地快速排序
def quicksort_inplace(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort_inplace(arr, low, pivot_index - 1)
        quicksort_inplace(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

归并排序

python复制
def mergesort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

算法复杂度分析

时间复杂度

python复制
# O(1) - 常数时间
def get_first_element(lst):
    return lst[0]

# O(n) - 线性时间
def find_max(lst):
    max_val = lst[0]
    for val in lst:
        if val > max_val:
            max_val = val
    return max_val

# 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]

# O(log n) - 对数时间（二分查找）
# O(n log n) - 线性对数时间（归并排序、快速排序平均情况）

空间复杂度

python复制
# O(1) - 原地算法
def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# O(n) - 需要额外空间
def create_squares(n):
    return [i * i for i in range(n)]

# O(log n) - 递归调用栈空间（二分查找的递归实现）
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

常见面试问题

Q1: Python 列表和链表的区别？

Q2: 什么时候用 list vs deque？

• list：需要随机访问（按索引）、在尾部操作
• deque：需要在头尾两端操作、BFS 算法

python复制
from collections import deque

# BFS 使用 deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        node = queue.popleft()  # O(1)
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node])

Q3: 如何选择排序算法？

• 小数据量（< 50）：插入排序（简单，实现快）
• 一般情况：Python 内置 sorted()（TimSort，O(n log n)）
• 需要稳定排序：归并排序
• 需要最快平均：快速排序
• 数据接近有序：插入排序