Blog of AgioPan
0%

数据结构与算法自学笔记（13）- 数据结构设计高频题

Posted on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class035的内容，总结了数据结构设计类题目的高频考点，包含7道经典数据结构设计题目的详细解析。这些题目主要基于哈希表的O(1)操作时间复杂度特性。

前置知识

在学习数据结构设计高频题之前，需要掌握以下基础知识：

  • 动态数组和扩容分析（007讲）
  • 链表入门内容（009~012讲）
  • 堆结构（025讲）
  • 哈希表、有序表、比较器的使用（026讲）

重要说明

本节以数据结构设计高频题为主，并不涉及太难的数据结构设计题目，很多题的原理都是基于哈希表的O(1)时间复杂度。数据结构设计的更难题目，需要学习更多数据结构之后才能解决，如前缀树、并查集、线段树等。

035【必备】数据结构设计高频题

题目一：setAll功能的哈希表

问题描述

哈希表常见的三个操作是put、get和containsKey，而且这三个操作的时间复杂度为O(1)。现在想加一个setAll功能，就是把所有记录value都设成统一的值。请设计并实现这种有setAll功能的哈希表，并且put、get、containsKey和setAll四个操作的时间复杂度都为O(1)。

测试链接：https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967

核心思想

采用”懒更新”(Lazy Update)策略，setAll操作只记录一个全局值和当前时间戳，并不实际修改数据。当get一个键时，通过比较该键自身的时间戳和全局setAll的时间戳，来实时决定返回它自己的值还是全局的值。

为hash表设置setall方法

算法实现

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
class SetAllHashMap:
    def __init__(self):
        # 核心数据结构，存储键和它对应的值与时间戳
        # 格式为: { key: [value, time] }
        self.map = {}
        # setAll操作设定的统一值
        self.set_all_value = 0
        # setAll操作发生的时间戳
        self.set_all_time = -1
        # 全局时间戳，用于记录每次操作的顺序
        self.cnt = 0

    def put(self, k, v):
        # 核心思想：为每个put操作记录一个独立的时间戳
        if k in self.map:
            # 如果键已存在，更新其值和时间戳
            value = self.map[k]
            value[0] = v
            value[1] = self.cnt
            self.cnt += 1
        else:
            # 如果键不存在，创建新的条目
            self.map[k] = [v, self.cnt]
            self.cnt += 1

    def set_all(self, v):
        # 核心思想：只记录setAll的值和时间戳，不实际遍历map
        # 这是一个懒更新策略，只有在get的时候才根据时间戳判断
        self.set_all_value = v
        self.set_all_time = self.cnt
        self.cnt += 1

    def get(self, k):
        # 核心思想：比较单个key的更新时间和全局setAll的更新时间
        if k not in self.map:
            return -1
        
        value = self.map[k]
        # 如果这个key的最后更新时间晚于setAll的时间，说明它的值是有效的
        if value[1] > self.set_all_time:
            return value[0]
        # 否则，它的值已经被setAll覆盖了，应返回setAll的值
        else:
            return self.set_all_value

高效读写

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
def main():
    # 创建一个SetAllHashMap对象，模拟带有setAll操作的哈希表，模拟牛客网的输入输出处理
    solution = SetAllHashMap()
    # 读取所有输入行（提高输入效率）
    lines = sys.stdin.readlines()
    i = 0
    while i < len(lines): # 遍历所有行
        line = lines[i].strip()
        if not line:
            # 跳过空行
            i += 1
            continue

        # 读取本组操作数n
        n = int(line)
        # 每个测试用例开始前重置数据结构
        solution.__init__()

        # 连续读取n行操作
        for j in range(n):
            i += 1
            # 解析当前操作的所有参数，map是把字符串转换成列表，int指明了列表的元素类型
            parts = list(map(int, lines[i].strip().split()))
            op = parts[0]
            if op == 1:
                # op=1，put操作，后面有两个参数a, b
                a, b = parts[1], parts[2]
                solution.put(a, b)
            elif op == 2:
                # op=2，get操作，后面一个参数a
                a = parts[1]
                print(solution.get(a))
            else:
                # op=3，setAll操作，后面一个参数a
                a = parts[1]
                solution.set_all(a)
        # 处理完一组数据，i+1进入下一组或结束
        i += 1

if __name__ == "__main__":
    # 在提交时，类名需要改为 Main
    main()

算法分析

  • 时间复杂度：所有操作都是O(1)
  • 空间复杂度：O(N)，N为键的数量
  • 核心技巧：时间戳比较 + 懒更新策略

题目二：实现LRU结构

问题描述

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量capacity初始化LRU缓存
  • int get(int key) 如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
  • void put(int key, int value) 如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字

函数get和put必须以O(1)的平均时间复杂度运行。

测试链接：https://leetcode.cn/problems/lru-cache/

核心思想

结合了哈希表和双向链表：哈希表提供了对任意键的O(1)快速访问，而双向链表则负责维护数据的访问顺序，使其能在O(1)时间内将最新访问的节点移到队尾，并在容量满时淘汰队首的最久未使用节点。

lru结构的实现

算法实现

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class LRUCache:
    # 内部类，定义双向链表节点
    class DoubleNode:
        def __init__(self, key=0, val=0):
            self.key = key
            self.val = val
            self.last = None
            self.next = None

    # 内部类，实现双向链表，用于维护节点的访问顺序
    class DoubleList:
        def __init__(self):
            # 哨兵节点，简化边界条件处理
            self.head = self.DoubleNode() #头节点
            self.tail = self.DoubleNode() #尾节点
            self.head.next = self.tail #头节点的下一个节点是尾节点
            self.tail.last = self.head #尾节点的上一个节点是头节点

        # 将一个节点添加到链表尾部（表示最近使用）
        def add_node_to_tail(self, node):
            node.next = self.tail # 将新节点添加到尾节点的前一个位置
            node.last = self.tail.last # 将新节点的上一个节点设置为尾节点的前一个节点
            self.tail.last.next = node # 将尾节点的前一个节点的下一个节点设置为新节点
            self.tail.last = node # 将尾节点的前一个节点设置为新节点
            # 这样设置是为了把尾节点和前一个节点的两条指针变成四条指针

        # 将指定节点移动到链表尾部
        def move_node_to_tail(self, node):
            # 先将节点从原位置断开
            node.last.next = node.next
            node.next.last = node.last
            # 再将节点添加到尾部
            self.add_node_to_tail(node)

        # 移除链表头部节点（最久未使用的节点）并返回
        def remove_head(self):
            # 如果链表为空（只有哨兵节点），则无法移除
            if self.head.next == self.tail:
                return None
            node_to_remove = self.head.next
            # 从链表中移除
            node_to_remove.last.next = node_to_remove.next
            node_to_remove.next.last = node_to_remove.last
            return node_to_remove

    def __init__(self, capacity: int):
        # 核心思想：使用哈希表实现O(1)查找，使用双向链表实现O(1)的节点移动（更新访问顺序）
        # 哈希表，存储 key -> DoubleNode 的映射
        self.key_node_map = {}
        # 双向链表实例，维护节点的LRU顺序
        self.node_list = self.DoubleList()
        # 缓存的容量
        self.capacity = capacity

    def get(self, key: int) -> int:
        # 如果key存在
        if key in self.key_node_map:
            # 获取节点
            node = self.key_node_map[key]
            # 将该节点移动到链表尾部，表示最近被访问
            self.node_list.move_node_to_tail(node)
            return node.val
        # 如果key不存在，返回-1
        return -1

    def put(self, key: int, value: int) -> None:
        # 如果key已存在
        if key in self.key_node_map:
            # 更新节点的值
            node = self.key_node_map[key]
            node.val = value
            # 将该节点移动到链表尾部
            self.node_list.move_node_to_tail(node)
        else:
            # 如果缓存已满
            if len(self.key_node_map) == self.capacity:
                # 移除链表头部的最久未使用节点，之后会再把新节点添加到尾部
                removed_node = self.node_list.remove_head()
                # 从哈希表中删除对应的key
                del self.key_node_map[removed_node.key]
            
            # 创建新节点
            new_node = self.DoubleNode(key, value)
            # 存入哈希表
            self.key_node_map[key] = new_node
            # 将新节点添加到链表尾部
            self.node_list.add_node_to_tail(new_node)

算法分析

  • 时间复杂度：get和put操作都是O(1)
  • 空间复杂度：O(capacity)
  • 核心技巧：哈希表 + 双向链表

题目三：插入、删除和获取随机元素O(1)时间的结构

问题描述

设计一个支持在平均时间复杂度O(1)下，执行以下操作的数据结构：

  • insert(val)：当元素val不存在时，向集合中插入该项
  • remove(val)：元素val存在时，从集合中移除该项
  • getRandom()：随机返回现有集合中的一项

测试链接：https://leetcode.cn/problems/insert-delete-getrandom-o1/

核心思想

结合了动态数组与哈希表，数组负责存储元素以实现O(1)的随机获取，哈希表则存储”值到数组索引”的映射以实现O(1)的查找。其remove操作的精髓在于：将待删除元素与数组的最后一个元素交换，然后直接删除数组末尾。

hash表加入移除和得到随机索引

算法实现

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
import random

class RandomizedSet:
    def __init__(self):
        # 核心思想：
        # 1. 使用哈希表（字典）存储 值 -> 索引 的映射，实现O(1)的查找。
        # 2. 使用动态数组（列表）存储值，实现O(1)的随机访问。
        self.map = {}  
        self.arr = []

    def insert(self, val: int) -> bool:
        # 如果值已存在，直接返回False
        if val in self.map:
            return False
        # 将值添加到数组末尾
        self.arr.append(val)
        # 在哈希表中记录新值及其索引,map[val]返回val在数组中的索引
        self.map[val] = len(self.arr) - 1
        return True

    def remove(self, val: int) -> bool:
        # 如果值不存在，直接返回False
        if val not in self.map:
            return False
        
        # 核心步骤：为了实现O(1)删除，将被删除元素与数组末尾元素交换，然后删除末尾元素。
        # 获取待删除元素的索引
        val_index = self.map[val]
        # 获取数组末尾的元素
        end_value = self.arr[-1]
        
        # 将末尾元素放到待删除元素的位置
        self.arr[val_index] = end_value
        # 更新哈希表中末尾元素的索引，只更新索引不更新值
        self.map[end_value] = val_index
        
        # 从哈希表中删除目标值
        del self.map[val]
        # 从数组中删除末尾元素，两者同步更新
        self.arr.pop()
        
        return True

    def getRandom(self) -> int:
        # 利用数组的特性，随机选择一个索引并返回对应的值
        return random.choice(self.arr)

算法分析

  • 时间复杂度：所有操作都是O(1)
  • 空间复杂度：O(N)
  • 核心技巧：数组末尾交换删除

题目四：插入、删除和获取随机元素O(1)时间且允许重复数字的结构

问题描述

设计一个支持在平均时间复杂度O(1)下，执行以下操作的数据结构，且允许有重复数字：

  • insert(val)：向集合中插入元素val
  • remove(val)：从集合中移除元素val的一个实例
  • getRandom()：随机返回现有集合中的一项

测试链接：https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/

核心思想

与不允许重复的版本类似，但哈希表需要存储一个值所有出现位置的索引集合。

算法实现

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
import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        # 核心思想：与不允许重复的版本类似，但哈希表需要存储一个值所有出现位置的索引集合。
        # 注意：字典中每个key指向的是不同的集合(set)，而不是同一个数组
        # 字典：存储 值 -> 索引集合 的映射
        self.map = defaultdict(set)
        # 列表：存储所有值
        self.arr = []

    def insert(self, val: int) -> bool:
        # 判断是否是第一次插入该值
        is_new = val not in self.map
        # 将值添加到数组末尾
        self.arr.append(val)
        # 在哈希表中记录新值的索引
        self.map[val].add(len(self.arr) - 1)
        return is_new

    def remove(self, val: int) -> bool:
        # 如果值不存在，无法删除
        if val not in self.map:
            return False

        # 核心步骤：同样是与末尾元素交换以实现O(1)删除
        # 获取待删除值的一个索引
        val_index = self.map[val].pop()
        # 获取末尾元素的值和索引
        end_value = self.arr[-1]
        end_index = len(self.arr) - 1

        # 如果待删除的元素恰好是末尾元素，则不需要交换
        if val_index != end_index:
            # 用末尾元素覆盖待删除元素的位置
            self.arr[val_index] = end_value
            # 更新末尾元素在哈希表中的索引记录
            self.map[end_value].remove(end_index) 
            self.map[end_value].add(val_index)
            #这里的 map 是一个存储集合的集合，所以需要通过 map[key] 先获取到集合，然后对集合调用 remove() 和 add() 方法。这是 Python 中嵌套数据结构的常见操作模式。
        # 从数组中移除末尾元素
        self.arr.pop()
        
        # 如果移除后，某个值的索引集合为空，则从哈希表中彻底删除该值
        if not self.map[val]:
            del self.map[val]
            
        return True

    def getRandom(self) -> int:
        # 随机获取一个元素
        return random.choice(self.arr)

算法分析

  • 时间复杂度：所有操作都是O(1)
  • 空间复杂度：O(N)
  • 核心技巧：索引集合管理

题目五：快速获得数据流的中位数的结构

问题描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，[2,3,4]的中位数是3，[2,3]的中位数是(2 + 3) / 2 = 2.5

设计一个支持以下两个操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中
  • double findMedian() - 返回目前所有元素的中位数

测试链接：https://leetcode.cn/problems/find-median-from-data-stream/

核心思想

使用两个堆来维护数据流，一个大顶堆和一个小顶堆。大顶堆存储数据流中较小的一半数字，小顶堆存储数据流中较大的一半数字。这样，中位数总是可以通过两个堆的堆顶元素快速得到。

找中位数

算法实现

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
import heapq

class MedianFinder:
    def __init__(self):
        # 核心思想：使用两个堆来维护数据流，一个大顶堆和一个小顶堆。
        # 大顶堆 (max_heap) 存储数据流中较小的一半数字。
        # 小顶堆 (min_heap) 存储数据流中较大的一半数字。
        # 这样，中位数总是可以通过两个堆的堆顶元素快速得到。
        
        # Python的heapq是小顶堆，为了实现大顶堆，我们存入元素的相反数。
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        # 步骤1: 决定将新元素添加到哪个堆。
        # 如果大顶堆为空，或者新元素小于等于大顶堆的堆顶，则放入大顶堆。
        # 否则，放入小顶堆。
        if not self.max_heap or -self.max_heap[0] >= num:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)
        
        # 步骤2: 平衡两个堆的大小，确保它们的size之差不超过1。
        self._balance()

    def findMedian(self) -> float:
        # 根据两个堆的大小来计算中位数。
        # 如果大小相等（总元素为偶数），中位数是两个堆顶的平均值。
        if len(self.max_heap) == len(self.min_heap):
            # 注意从大顶堆取值时要取反，恢复其原始值。
            return (-self.max_heap[0] + self.min_heap[0]) / 2.0
        # 如果大小不等（总元素为奇数），中位数就是那个size更大的堆的堆顶。
        else:
            return -self.max_heap[0] if len(self.max_heap) > len(self.min_heap) else self.min_heap[0]

    # 私有辅助方法，用于平衡两个堆
    def _balance(self) -> None:
        # 当两个堆的大小差距为2时，需要从元素多的堆移动一个到元素少的堆。
        if abs(len(self.max_heap) - len(self.min_heap)) == 2:
            if len(self.max_heap) > len(self.min_heap):
                heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
            else:
                heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

算法分析

  • 时间复杂度：addNum为O(logN)，findMedian为O(1)
  • 空间复杂度：O(N)
  • 核心技巧：双堆平衡

题目六：最大频率栈

问题描述

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类：

  • FreqStack() 构造一个空的堆栈
  • void push(int val) 将一个整数val压入栈顶
  • int pop() 删除并返回堆栈中出现频率最高的元素

测试链接：https://leetcode.cn/problems/maximum-frequency-stack/

核心思想

使用一个哈希表记录每个值出现的频率，使用另一个哈希表将频率映射到一个栈，这个栈存储了所有出现该频率的数字。使用一个变量实时追踪当前的最大频率。

最高频率栈

算法实现

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
from collections import defaultdict

class FreqStack:
    def __init__(self): #这个初始化的是hashmap
        # 核心思想:
        # 1. 使用一个哈希表 (value_times) 记录每个值出现的频率。
        # 2. 使用另一个哈希表 (cnt_values) 将频率映射到一个栈（列表），这个栈存储了所有出现该频率的数字。
        # 3. 使用一个变量 (top_times) 实时追踪当前的最大频率。
        # pop操作总是从最大频率对应的栈中弹出元素，这保证了既是最高频也是最“新”的。

        # 出现的最大次数
        self.top_times = 0
        # 每层节点 (每个频率有哪些数)
        # defaultdict(list) 会在key不存在时自动创建一个空列表
        self.cnt_values = defaultdict(list) 
        # 每一个数出现了几次
        # defaultdict(int) 会在key不存在时自动创建一个0
        self.value_times = defaultdict(int) 
        #实际上，cnt_values和value_times是两个哈希表，一个存储频率，一个存储频率对应的数

    def push(self, val: int) -> None:
        # 步骤1: 更新该值的频率
        self.value_times[val] += 1
        current_freq = self.value_times[val]
        
        # 步骤2: 将该值压入其新频率对应的栈中
        self.cnt_values[current_freq].append(val)
        
        # 步骤3: 更新全局最大频率
        self.top_times = max(self.top_times, current_freq)

    def pop(self) -> int:
        # 步骤1: 从最大频率对应的栈中弹出最近压入的元素
        ans = self.cnt_values[self.top_times].pop()
        
        # 步骤2: 如果弹出后，该频率的栈为空了，说明最大频率需要降低
        if not self.cnt_values[self.top_times]:
            self.top_times -= 1
        
        # 步骤3: 更新被弹出元素自身的频率记录
        self.value_times[ans] -= 1
        
        return ans

算法分析

  • 时间复杂度：push和pop操作都是O(1)
  • 空间复杂度：O(N)
  • 核心技巧：频率分层存储

题目七：全O(1)的数据结构

问题描述

请你实现一个数据结构支持以下操作：

  • Inc(key) - 插入一个新的值为1的key，或者使一个存在的key增加一，保证key不为空字符串
  • Dec(key) - 如果这个key的值是1，那么把他从数据结构中移除掉。否则使一个存在的key值减一。如果这个key不存在，这个函数不做任何事情。key保证不为空字符串
  • GetMaxKey() - 返回key中值最大的任意一个。如果没有元素存在，返回一个空字符串””
  • GetMinKey() - 返回key中值最小的任意一个。如果没有元素存在，返回一个空字符串””

挑战：以O(1)的时间复杂度实现所有操作。

测试链接：https://leetcode.cn/problems/all-oone-data-structure/

核心思想

使用一个双向链表来组织桶(Bucket)，链表按桶的计数值(cnt)升序排列。每个桶包含一个集合，存储所有计数值等于该桶cnt的key。使用一个哈希表来存储key -> Bucket的映射，实现O(1)的key定位。

all1类

算法实现

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
class AllOne:
    # 内部类，定义双向链表的节点，也叫“桶”
    # 每个桶存储具有相同计数值的所有key
    class Bucket:
        def __init__(self, cnt):
            self.cnt = cnt
            self.keys = set()
            self.last = None
            self.next = None

    def __init__(self):
        # 核心思想:
        # 1. 使用一个双向链表来组织桶(Bucket)，链表按桶的计数值(cnt)升序排列。
        # 2. 每个桶(Bucket)包含一个集合(set)，存储所有计数值等于该桶cnt的key。
        # 3. 使用一个哈希表(map)来存储 key -> Bucket 的映射，实现O(1)的key定位。
        # inc/dec操作本质上是将key从一个桶移动到相邻的下一个/上一个桶。
        
        # 创建头尾哨兵节点，简化边界处理
        self.head = self.Bucket(0)
        self.tail = self.Bucket(float('inf'))
        # 将头节点的下一个指针指向尾节点，尾节点的上一个指针指向头节点，这样操作后，双向链表形成了一个初始的空结构：head <-> tail
        self.head.next = self.tail
        self.tail.last = self.head
        # 存储 key 到其所在 Bucket 的映射
        self.map = {}

    # 辅助函数：在指定位置(prev_bucket)后插入一个新桶(new_bucket)
    def _insert_after(self, prev_bucket, new_bucket):
        new_bucket.next = prev_bucket.next
        new_bucket.last = prev_bucket
        prev_bucket.next.last = new_bucket
        prev_bucket.next = new_bucket

    # 辅助函数：从链表中移除一个桶，让前后的指针跳过当前桶
    def _remove_bucket(self, bucket):
        bucket.last.next = bucket.next
        bucket.next.last = bucket.last

    def inc(self, key: str) -> None:
        # 核心步骤：将key从当前桶移动到cnt+1的桶
        if key not in self.map:
            # case 1: 新key，计数值为1
            # 找到或创建cnt=1的桶
            target_bucket = self.head.next #定位到第一个桶
            if target_bucket.cnt != 1:
                target_bucket = self.Bucket(1)
                self._insert_after(self.head, target_bucket)
            # 将key加入桶和map
            target_bucket.keys.add(key)
            self.map[key] = target_bucket
        else:
            # case 2: key已存在
            current_bucket = self.map[key] #map是双向的
            new_cnt = current_bucket.cnt + 1
            
            # 找到或创建cnt=new_cnt的桶
            target_bucket = current_bucket.next
            if target_bucket.cnt != new_cnt:
                target_bucket = self.Bucket(new_cnt)
                self._insert_after(current_bucket, target_bucket)

            # 移动key
            target_bucket.keys.add(key)
            self.map[key] = target_bucket
            current_bucket.keys.remove(key)
            
            # 如果原桶变空，则移除
            if not current_bucket.keys:
                self._remove_bucket(current_bucket)

    def dec(self, key: str) -> None:
        if key not in self.map:
            return
        
        # 核心步骤：将key从当前桶移动到cnt-1的桶
        current_bucket = self.map[key]
        current_bucket.keys.remove(key)

        if current_bucket.cnt > 1:
            new_cnt = current_bucket.cnt - 1
            # 找到或创建cnt=new_cnt的桶
            target_bucket = current_bucket.last
            if target_bucket.cnt != new_cnt:
                target_bucket = self.Bucket(new_cnt)
                self._insert_after(current_bucket.last, target_bucket)
            # 移动key
            target_bucket.keys.add(key)
            self.map[key] = target_bucket
        else:
            # 如果cnt为1，dec后直接从map中移除
            del self.map[key]
        
        # 如果原桶变空，则移除
        if not current_bucket.keys:
            self._remove_bucket(current_bucket)

    def getMaxKey(self) -> str:
        # 最大计数值的桶在tail哨兵节点的前面
        if self.tail.last == self.head:
            return ""
        # 从桶的集合中任意取一个key即可
        return next(iter(self.tail.last.keys)) 
        # self.tail.last - 获取尾哨兵节点的前一个节点，也就是链表中最后一个实际的桶
        # .keys - 这个桶中存储的键的集合（set）
        # iter(...) - 将集合转换为迭代器
        # next(...) - 从迭代器中获取第一个元

    def getMinKey(self) -> str:
        # 最小计数值的桶在head哨兵节点的后面
        if self.head.next == self.tail:
            return ""
        # 从桶的集合中任意取一个key即可
        return next(iter(self.head.next.keys))

算法分析

  • 时间复杂度：所有操作都是O(1)
  • 空间复杂度：O(N)
  • 核心技巧：双向链表 + 桶分组

数据结构设计核心技巧总结

1. 哈希表的O(1)特性

大部分设计题都基于哈希表的O(1)查找、插入、删除特性：

1
2
3
4
5
# 基本哈希表操作
hash_map = {}
hash_map[key] = value  # O(1) 插入
val = hash_map[key]    # O(1) 查找
del hash_map[key]      # O(1) 删除

2. 时间戳技巧

用于实现懒更新策略：

1
2
3
4
5
# 时间戳比较
if operation_time > global_time:
    return local_value
else:
    return global_value

3. 双向链表维护顺序

适用于需要频繁移动元素位置的场景：

1
2
3
4
5
6
7
8
9
10
# 双向链表节点移动
def move_to_tail(node):
    # 断开原连接
    node.prev.next = node.next
    node.next.prev = node.prev
    # 插入到尾部
    node.next = tail
    node.prev = tail.prev
    tail.prev.next = node
    tail.prev = node

4. 数组末尾交换删除

实现O(1)删除的经典技巧：

1
2
3
4
# 将待删除元素与末尾元素交换
arr[del_index] = arr[-1]
map[arr[-1]] = del_index  # 更新索引映射
arr.pop()  # 删除末尾元素

5. 双堆维护极值

适用于动态维护中位数或其他统计量：

1
2
3
4
# 维护两个堆的平衡
if abs(len(max_heap) - len(min_heap)) > 1:
    # 从大的堆移动元素到小的堆
    balance_heaps()

复杂度分析总结

题目 时间复杂度 空间复杂度 核心数据结构
setAll哈希表 O(1) O(N) 哈希表+时间戳
LRU缓存 O(1) O(capacity) 哈希表+双向链表
随机数据结构 O(1) O(N) 哈希表+动态数组
随机数据结构(重复) O(1) O(N) 哈希表+集合+数组
中位数查找 O(logN)/O(1) O(N) 双堆
最大频率栈 O(1) O(N) 哈希表+栈数组
全O(1)数据结构 O(1) O(N) 哈希表+双向链表+桶

学习建议

  1. 理解O(1)的本质：大多数设计题的核心是利用哈希表的O(1)特性

  2. 掌握组合数据结构：

    • 哈希表 + 双向链表（LRU）
    • 哈希表 + 动态数组（随机访问）
    • 双堆（维护极值）
    • 时间戳（懒更新）

  3. 注意边界条件：

    • 空数据结构
    • 容量限制
    • 重复元素处理

  4. 理解权衡取舍：

    • 时间复杂度 vs 空间复杂度
    • 实现复杂度 vs 运行效率

  5. 多练习组合技巧：数据结构设计题往往需要组合多种基础数据结构

数据结构设计题考察的是对基础数据结构的深入理解和灵活运用能力。通过掌握这些经典模式和技巧，可以应对大多数设计类问题。