基础数据结构与排序
本章节整理自 jwasham/coding-interview-university，重点关注面试中的实现要求。
更多内容请参考：数据结构 - 理论讲解与算法分析
数组 (Array)
实现要求
| 方法 | 说明 | 时间复杂度 |
|---|---|---|
size() | 返回元素数量 | O(1) |
capacity() | 返回容量大小 | O(1) |
is_empty() | 是否为空 | O(1) |
at(index) | 返回指定索引元素，超界报错 | O(1) |
push(item) | 末尾添加元素 | O(1) 均摊 |
insert(index, item) | 指定位置插入 | O(n) |
prepend(item) | 头部插入（用 insert） | O(n) |
pop() | 末尾删除并返回 | O(1) 均摊 |
delete(index) | 指定位置删除 | O(n) |
remove(item) | 删除所有匹配项 | O(n) |
find(item) | 查找元素，返回首次索引 | O(n) |
resize(new_capacity) | 扩容/缩容 | O(n) |
关键实现细节
python
class Array:
def __init__(self, initial_capacity=16):
self.capacity = initial_capacity if initial_capacity >= 16 else 16
self.size = 0
self.data = [None] * self.capacity
def _resize(self, new_capacity):
"""动态扩容"""
new_data = [None] * new_capacity
for i in range(self.size):
new_data[i] = self.data[i]
self.data = new_data
self.capacity = new_capacity
def push(self, item):
"""末尾添加，均摊 O(1)"""
if self.size == self.capacity:
self._resize(self.capacity * 2) # 容量翻倍
self.data[self.size] = item
self.size += 1
def pop(self):
"""末尾删除，均摊 O(1)"""
if self.size == 0:
return None
item = self.data[self.size - 1]
self.size -= 1
# 缩容：当 size 为容量的 1/4 时，缩到一半
if self.size > 0 and self.size == self.capacity // 4:
self._resize(self.capacity // 2)
return item复杂度
| 操作 | 时间复杂度 |
|---|---|
| 尾部添加/删除 | O(1) 均摊 |
| 按索引访问 | O(1) |
| 任意位置插入/删除 | O(n) |
| 空间 | O(n) |
链表 (Linked List)
单链表实现要求
| 方法 | 说明 | 时间复杂度 |
|---|---|---|
size() | 返回元素数量 | O(1) 或 O(n) |
empty() | 是否为空 | O(1) |
value_at(index) | 返回第 n 个元素 | O(n) |
push_front(value) | 头部插入 | O(1) |
pop_front() | 头部删除并返回值 | O(1) |
push_back(value) | 尾部插入 | O(1) 或 O(n) |
pop_back() | 尾部删除并返回值 | O(n) 或 O(1) |
front() | 获取头部元素 | O(1) |
back() | 获取尾部元素 | O(1) 或 O(n) |
insert(index, value) | 指定位置插入 | O(n) |
erase(index) | 删除指定位置 | O(n) |
value_n_from_end(n) | 返回倒数第 n 个 | O(n) |
reverse() | 反转链表 | O(n) |
remove_value(value) | 删除第一个匹配项 | O(n) |
Python 实现
python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None # 尾指针优化
self.size = 0
def push_front(self, value):
"""O(1)"""
node = Node(value)
node.next = self.head
self.head = node
if self.tail is None:
self.tail = node
self.size += 1
def pop_front(self):
"""O(1)"""
if self.head is None:
return None
value = self.head.value
self.head = self.head.next
if self.head is None:
self.tail = None
self.size -= 1
return value
def push_back(self, value):
"""O(1) with tail pointer"""
node = Node(value)
if self.tail:
self.tail.next = node
self.tail = node
else:
self.head = self.tail = node
self.size += 1
def reverse(self):
"""反转链表 O(n)"""
prev = None
curr = self.head
self.tail = self.head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
self.head = prev链表 vs 数组
| 特性 | 链表 | 数组 |
|---|---|---|
| 随机访问 | O(n) | O(1) |
| 头部插入/删除 | O(1) | O(n) |
| 尾部插入 | O(1) | O(1) 均摊 |
| 中间插入 | O(n) | O(n) |
| 空间开销 | O(n) + 指针 | O(n) 连续内存 |
栈 (Stack)
实现要求
| 方法 | 说明 |
|---|---|
push(item) | 入栈 |
pop() | 出栈并返回 |
peek() | 查看栈顶 |
is_empty() | 是否为空 |
实现：使用数组
python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.items:
return None
return self.items.pop()
def peek(self):
return self.items[-1] if self.items else None
def is_empty(self):
return len(self.items) == 0复杂度
| 操作 | 时间复杂度 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
队列 (Queue)
实现要求
| 方法 | 说明 |
|---|---|
enqueue(value) | 入队 |
dequeue() | 出队并返回 |
empty() | 是否为空 |
实现：链表 + 尾指针
python
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, value):
node = Node(value)
if self.tail:
self.tail.next = node
self.tail = node
else:
self.head = self.tail = node
def dequeue(self):
if self.head is None:
return None
value = self.head.value
self.head = self.head.next
if self.head is None:
self.tail = None
return value
def empty(self):
return self.head is None实现：循环缓冲区（固定大小数组）
python
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity
self.queue = [None] * capacity
self.head = 0
self.tail = 0
self.size = 0
def enqueue(self, value):
if self.size == self.capacity:
return False
self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.capacity
self.size += 1
return True
def dequeue(self):
if self.size == 0:
return None
value = self.queue[self.head]
self.head = (self.head + 1) % self.capacity
self.size -= 1
return value
def empty(self):
return self.size == 0
def full(self):
return self.size == self.capacity哈希表 (Hash Table)
实现要求
| 方法 | 说明 |
|---|---|
hash(key, m) | 哈希函数 |
add(key, value) | 添加/更新 |
exists(key) | 键是否存在 |
get(key) | 获取值 |
remove(key) | 删除 |
实现：线性探测 + 数组
python
class HashTable:
def __init__(self, size=16):
self.size = size
self.keys = [None] * size
self.values = [None] * size
def _hash(self, key):
"""简单哈希函数"""
return hash(key) % self.size
def add(self, key, value):
"""线性探测解决冲突"""
index = self._hash(key)
start_index = index
while self.keys[index] is not None:
if self.keys[index] == key:
self.values[index] = value
return
index = (index + 1) % self.size
if index == start_index:
raise Exception("Hash table is full")
self.keys[index] = key
self.values[index] = value
def get(self, key):
index = self._hash(key)
start_index = index
while self.keys[index] is not None:
if self.keys[index] == key:
return self.values[index]
index = (index + 1) % self.size
if index == start_index:
break
return None
def remove(self, key):
index = self._hash(key)
start_index = index
while self.keys[index] is not None:
if self.keys[index] == key:
self.keys[index] = None
self.values[index] = None
return True
index = (index + 1) % self.size
if index == start_index:
break
return False
def exists(self, key):
return self.get(key) is not None复杂度
| 操作 | 平均 | 最坏 |
|---|---|---|
| 查找 | O(1) | O(n) |
| 插入 | O(1) | O(n) |
| 删除 | O(1) | O(n) |
排序算法
面试必会排序
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✓ |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ✗ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ✗ |
| 插入排序 | O(n²) | O(n²) | O(1) | ✓ |
| 选择排序 | O(n²) | O(n²) | O(1) | ✗ |
NOTE
冒泡排序除非 n<=16，否则不要使用。
归并排序实现
python
def merge_sort(arr):
"""O(n log n), 稳定"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(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
def quick_sort(arr):
"""O(n log n) 平均, 不稳定"""
_quick_sort(arr, 0, len(arr) - 1)
return arr
def _quick_sort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
_quick_sort(arr, low, pivot_index - 1)
_quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
"""三数取中优化"""
mid = (low + high) // 2
# 将中位数放到高位
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[low]:
arr[mid], arr[low] = arr[low], arr[mid]
pivot = arr[low]
i = low + 1
j = high
while True:
while i <= j and arr[i] <= pivot:
i += 1
while i <= j and arr[j] >= pivot:
j -= 1
if i > j:
break
arr[i], arr[j] = arr[j], arr[i]
arr[low], arr[j] = arr[j], arr[low]
return j堆排序实现
python
def heap_sort(arr):
"""O(n log n), 不稳定"""
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)
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)稳定性
| 算法 | 稳定性 |
|---|---|
| 归并排序 | ✓ 稳定 |
| 插入排序 | ✓ 稳定 |
| 冒泡排序 | ✓ 稳定 |
| 快速排序 | ✗ 不稳定 |
| 堆排序 | ✗ 不稳定 |
| 选择排序 | ✗ 不稳定 |