全O(1)的数据结构:哈希表计数,支持查询计数最大与最小的键

  |  

摘要: 基于链表+哈希表解决与频数相关的设计问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文我们来看一个设计问题。在文章 设计-功能系统 中我们系统梳理过设计功能系统的问题。本文解决的问题是一个基于链表+哈希表进行设计的。这种链表+哈希表的设计方法还是比较经典的,例如 最大频率栈 也是一个类似的问题。

本题主要涉及到的算法如下:

  • 邻接表实现的桶结构
    • 桶的顺序用链表维护: 支持桶节点的插入删除
    • 桶内数据用链表维护: 支持数据节点的插入删除
  • 哈希索引: 支持桶节点和数据节点的查询

$1 题目

432. 全 O(1) 的数据结构

请你设计一个用于存储字符串计数的数据结构,并能够返回计数最小和最大的字符串。

实现 AllOne 类:

  • AllOne() 初始化数据结构的对象。
  • inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ,那么插入计数为 1 的 key 。
  • dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ,那么需要将这个 key 从数据结构中删除。测试用例保证:在减少计数前,key 存在于数据结构中。
  • getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在,返回一个空字符串 “” 。
  • getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在,返回一个空字符串 “” 。

注意:每个函数都应当满足 O(1) 平均时间复杂度。

提示:

1
2
3
4
1 <= key.length <= 10
key 由小写英文字母组成
测试用例保证:在每次调用 dec 时,数据结构中总存在 key
最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5e4 次

示例:
输入
[“AllOne”, “inc”, “inc”, “getMaxKey”, “getMinKey”, “inc”, “getMaxKey”, “getMinKey”]
[[], [“hello”], [“hello”], [], [], [“leet”], [], []]
输出
[null, null, null, “hello”, “hello”, null, “hello”, “leet”]
解释
AllOne allOne = new AllOne();
allOne.inc(“hello”);
allOne.inc(“hello”);
allOne.getMaxKey(); // 返回 “hello”
allOne.getMinKey(); // 返回 “hello”
allOne.inc(“leet”);
allOne.getMaxKey(); // 返回 “hello”
allOne.getMinKey(); // 返回 “leet”

$2 题解

算法: 哈希表 + 双向链表

我们要维护数据 key 以及对应的计数。对每个计数值,用一个桶来维护对应的元素,桶编号代表计数值。例如桶2中有元素 a, b,表示当前 a, b 这两个元素有两个,如果此时插入 a,则将 a 从桶 2 移入桶 3,如果删除 b,则将 b 从桶 2 移入桶 1。

要实现以上功能,可以设计以下结构。

(1) 邻接表实现的桶结构

  • 桶的顺序用链表维护: 支持桶节点的插入删除
  • 桶内数据用链表维护: 支持数据节点的插入删除

(2) 哈希索引: 支持桶节点和数据节点的查询

邻接表实现的桶结构

Ref: 邻接表

buckets 为邻接表实现的桶结构。每个桶有 valkeys 两个数据字段。

val 为桶的属性,这里表示桶内所有 key 对应的值。

keys 为数据链表:

1
2
3
4
5
6
7
8
9
10
11
list<Bucket> buckets;

struct Bucket
{
int val;
list<string> keys;
Bucket(int val):val(val)
{
keys = list<string>();
}
};

哈希索引

Ref: 加索引的链表

哈希索引结构建立从 key 到桶节点和数据节点的映射,mapping[key] 为 Index 结构体,内部持有两个字段,一个是桶节点的指针,另一个是数据节点的指针。

1
2
3
4
5
6
7
8
9
unordered_map<string, Index> mapping;

struct Index
{
list<Bucket>::iterator bucket_it;
list<string>::iterator key_it;
Index(list<Bucket>::iterator bucket_it, list<string>::iterator key_it):bucket_it(bucket_it),key_it(key_it){}
Index(){}
};

代码 (C++,模板)

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
struct Bucket
{
int val;
list<string> keys;
Bucket(int val):val(val)
{
keys = list<string>();
}
};

struct Index
{
list<Bucket>::iterator bucket_it;
list<string>::iterator key_it;
Index(list<Bucket>::iterator bucket_it, list<string>::iterator key_it):bucket_it(bucket_it),key_it(key_it){}
Index(){}
};

class AllOne {
public:
/** Initialize your data structure here. */
AllOne() {
buckets = list<Bucket>();
mapping = unordered_map<string, Index>();
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
void inc(string key) {
if(mapping.count(key) == 0)
{
if(buckets.empty() || buckets.front().val > 1)
buckets.emplace_front(1);
buckets.front().keys.push_back(key);
list<string>::iterator key_it = --buckets.front().keys.end();
list<Bucket>::iterator bucket_it = buckets.begin();
mapping[key] = Index(bucket_it, key_it);
}
else
{
Index idx = mapping[key];
int val = idx.bucket_it -> val;
auto nxt_bucket_it = next(idx.bucket_it, 1);
if(nxt_bucket_it == buckets.end() || nxt_bucket_it -> val > val + 1)
{
nxt_bucket_it = buckets.insert(nxt_bucket_it, Bucket(val + 1));
}
(nxt_bucket_it -> keys).push_back(key);
list<string>::iterator key_it = --(nxt_bucket_it -> keys).end();
mapping[key] = Index(nxt_bucket_it, key_it);
(idx.bucket_it -> keys).erase(idx.key_it);
if((idx.bucket_it -> keys).empty())
{
buckets.erase(idx.bucket_it);
}
}
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if(mapping.count(key) == 0)
return;
Index idx = mapping[key];
mapping.erase(key);
int val = idx.bucket_it -> val;
if(val == 1)
{
(idx.bucket_it -> keys).erase(idx.key_it);
if((idx.bucket_it -> keys).empty())
buckets.erase(idx.bucket_it);
}
else
{
auto prev_bucket_it = prev(idx.bucket_it, 1);
if(idx.bucket_it == buckets.begin() || prev_bucket_it -> val < val - 1)
{
prev_bucket_it = buckets.insert(idx.bucket_it, Bucket(val - 1));
}
(prev_bucket_it -> keys).push_back(key);
list<string>::iterator key_it = --(prev_bucket_it -> keys).end();
mapping[key] = Index(prev_bucket_it, key_it);
(idx.bucket_it -> keys).erase(idx.key_it);
if((idx.bucket_it -> keys).empty())
buckets.erase(idx.bucket_it);
}
}

/** Returns one of the keys with maximal value. */
string getMaxKey() {
if(buckets.empty())
return "";
return (buckets.back().keys).back();
}

/** Returns one of the keys with Minimal value. */
string getMinKey() {
if(buckets.empty())
return "";
return (buckets.front().keys).back();
}

private:
list<Bucket> buckets;
unordered_map<string, Index> mapping;
};

Share