算法数据结构

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

字数统计: 1.4k字   |   阅读时长: 6分
, , ,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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 为邻接表实现的桶结构。每个桶有 val 和 keys 两个数据字段。

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