【设计难题】力扣432-全O(1)的数据结构

  |  

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

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


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

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

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

$1 题目

题目链接

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

题目描述

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

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

$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