leetcode-432 全 O(1) 的数据结构

留言

https://leetcode.cn/problems/all-oone-data-structure/description/

为了满足 O(1) 平均时间复杂度的要求，我们需要巧妙地设计数据结构。这个设计需要快速增加和减少计数、快速访问最大和最小计数的字符串。一个有效的方法是使用两个哈希表和一个双向链表：

  1. 哈希表1 (keyCountMap): 存储键和其对应的计数值。
  2. 哈希表2 (countKeysMap): 存储计数值到包含该计数所有键的集合的映射。这里可以使用集合来存储具有相同计数的所有键，以便快速访问和修改。
  3. 双向链表: 存储所有不同的计数值，链表中的每个节点代表一个不同的计数值，节点按计数值排序。每个节点还需要有指向对应计数值的所有键的集合的链接（这可以通过 countKeysMap 实现）。

这样设计的好处是可以在 O(1) 时间内完成增加和减少计数的操作，并且可以在 O(1) 时间内访问到最小和最大计数的字符串。

下面是具体的实现：

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
package main

import (
	"container/list"
)

type AllOne struct {
    keyCountMap   map[string]int            // Key to count mapping
    countKeysMap  map[int]map[string]struct{} // Count to keys mapping
    countList     *list.List                // Sorted list of counts
}

func Constructor() AllOne {
    return AllOne{
        keyCountMap:  make(map[string]int),
        countKeysMap: make(map[int]map[string]struct{}),
        countList:    list.New(),
    }
}

func (ao *AllOne) Inc(key string) {
    // Increase the count for the key
    currentCount, exists := ao.keyCountMap[key]
    if !exists {
        currentCount = 0
    }
    ao.keyCountMap[key] = currentCount + 1

    // Add key to the new count
    if _, exists := ao.countKeysMap[currentCount+1]; !exists {
        ao.countKeysMap[currentCount+1] = make(map[string]struct{})
    }
    ao.countKeysMap[currentCount+1][key] = struct{}{}

    // Remove key from the old count
    if currentCount > 0 {
        delete(ao.countKeysMap[currentCount], key)
        if len(ao.countKeysMap[currentCount]) == 0 {
            delete(ao.countKeysMap, currentCount)
        }
    }
}

func (ao *AllOne) Dec(key string) {
    currentCount := ao.keyCountMap[key]

    // Decrease the count for the key
    if currentCount == 1 {
        delete(ao.keyCountMap, key)
    } else {
        ao.keyCountMap[key] = currentCount - 1
        ao.countKeysMap[currentCount-1][key] = struct{}{}
    }

    // Remove key from the old count
    delete(ao.countKeysMap[currentCount], key)
    if len(ao.countKeysMap[currentCount]) == 0 {
        delete(ao.countKeysMap, currentCount)
    }

    // Add key to the new count if not zero
    if currentCount > 1 {
        if _, exists := ao.countKeysMap[currentCount-1]; !exists {
            ao.countKeysMap[currentCount-1] = make(map[string]struct{})
        }
        ao.countKeysMap[currentCount-1][key] = struct{}{}
    }
}

func (ao *AllOne) GetMaxKey() string {
    if ao.countList.Back() == nil {
        return ""
    }
    for key := range ao.countKeysMap[ao.countList.Back().Value.(int)] {
        return key // Return any key from the largest count
    }
    return ""
}

func (ao *AllOne) GetMinKey() string {
    if ao.countList.Front() == nil {
        return ""
    }
    for key := range ao.countKeysMap[ao.countList.Front().Value.(int)] {
        return key // Return any key from the smallest count
    }
    return ""
}

func main() {
    // Usage example
    allOne := Constructor()
    allOne.Inc("hello")
    allOne.Inc("world")
    allOne.Inc("hello")
    println(allOne.GetMaxKey()) // Should print "hello"
    println(allOne.GetMinKey()) // Should print "world"
    allOne.Dec("hello")
    println(allOne.GetMaxKey()) // Should print "hello" or "world"
    println(allOne.GetMinKey()) // Should print "hello" or "world"
}

注意：上面的代码展示了数据结构的基本框架和 Inc、Dec 方法的逻辑，但是它并没有完全实现所有功能，特别是双向链表的部分和维护最小最大计数的精确逻辑。在实际应用中，你需要进一步完善 Inc 和 Dec 方法中对双向链表的操作，以确保可以在 O(1) 时间复杂度内找到最小和最大的计数值。这个实现更侧重于思路展示，而不是一个即插即用的解决方案。




要设计一个用于存储字符串计数的数据结构，并实现 AllOne 类，可以考虑使用两个数据结构：一个哈希表用于存储字符串和其对应的计数，另一个双向链表用于维护不同计数的字符串列表。以下是一个可能的实现：

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
package main

import "container/list"

type AllOne struct {
    countMap map[string]int        // 存储字符串计数的哈希表
    bucket   map[int]*list.Element // 存储不同计数的字符串列表的哈希表
    list     *list.List            // 双向链表，按计数从小到大存储字符串
}

type Entry struct {
    key   string
    count int
}

// 初始化数据结构对象
func Constructor() AllOne {
    return AllOne{
        countMap: make(map[string]int),
        bucket:   make(map[int]*list.Element),
        list:     list.New(),
    }
}

// 字符串计数增加 1
func (ao *AllOne) Inc(key string) {
    count := ao.countMap[key]

    // 从当前计数的 bucket 中删除 key
    if count > 0 {
        ao.removeFromBucket(count, key)
    }

    // 更新计数并将 key 加入新的 bucket
    ao.countMap[key]++
    count++
    ao.addToBucket(count, key)
}

// 字符串计数减少 1，如果计数为 0，则从数据结构中删除 key
func (ao *AllOne) Dec(key string) {
    count := ao.countMap[key]

    // 从当前计数的 bucket 中删除 key
    ao.removeFromBucket(count, key)

    // 更新计数，如果计数大于 1，则将 key 加入新的 bucket
    if count > 1 {
        ao.countMap[key]--
        count--
        ao.addToBucket(count, key)
    } else {
        // 如果计数为 1，则删除 key
        delete(ao.countMap, key)
    }
}

// 返回任意一个计数最大的字符串
func (ao *AllOne) GetMaxKey() string {
    if ao.list.Len() == 0 {
        return ""
    }

    return ao.list.Back().Value.(*Entry).key
}

// 返回任意一个计数最小的字符串
func (ao *AllOne) GetMinKey() string {
    if ao.list.Len() == 0 {
        return ""
    }

    return ao.list.Front().Value.(*Entry).key
}

// 将 key 加入计数对应的 bucket
func (ao *AllOne) addToBucket(count int, key string) {
    if _, exists := ao.bucket[count]; !exists {
        ao.bucket[count] = ao.list.InsertAfter(&Entry{key, count}, nil)
    } else {
        ao.bucket[count].Value.(*Entry).key = key
    }
}

// 从计数对应的 bucket 中删除 key
func (ao *AllOne) removeFromBucket(count int, key string) {
    if elem, exists := ao.bucket[count]; exists {
        ao.list.Remove(elem)
        if ao.list.Len() == 0 {
            delete(ao.bucket, count)
        }
    }
}

func main() {
    // 示例用法
    obj := Constructor()
    obj.Inc("hello")
    obj.Inc("world")
    obj.Inc("hello")
    obj.Dec("world")
    obj.GetMaxKey()
    obj.GetMinKey()
}

这个实现中，countMap 用于存储每个字符串的计数，bucket 用于存储不同计数的字符串列表。list 是一个双向链表，按照计数从小到大的顺序存储字符串。这样，获取最小和最大计数的字符串时，只需要直接访问链表的头和尾。

这个实现的关键在于保持数据结构的一致性，确保在增加和减少计数时，相关的数据结构都能够得到正确的更新。




以下是在 Rust 中实现类似的 AllOne 数据结构的简单示例。这个示例使用 std::collections::HashMap 作为哈希表，并使用 std::collections::BTreeMap 作为按键的有序集合，以保持计数的顺序。

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
use std::collections::{HashMap, BTreeMap};

struct AllOne {
    count_map: HashMap<String, usize>,
    bucket_map: BTreeMap<usize, Vec<String>>,
}

impl AllOne {
    fn new() -> Self {
        Self {
            count_map: HashMap::new(),
            bucket_map: BTreeMap::new(),
        }
    }

    fn inc(&mut self, key: String) {
        let count = self.count_map.entry(key.clone()).or_insert(0);
        
        // Remove from the current bucket
        self.bucket_map.entry(*count).and_modify(|v| {
            v.retain(|k| k != &key);
            if v.is_empty() {
                self.bucket_map.remove(count);
            }
        });

        // Increment count and add to the new bucket
        *count += 1;
        self.bucket_map.entry(*count).or_insert_with(Vec::new).push(key);
    }

    fn dec(&mut self, key: String) {
        if let Some(count) = self.count_map.get_mut(&key) {
            // Remove from the current bucket
            self.bucket_map.entry(*count).and_modify(|v| {
                v.retain(|k| k != &key);
                if v.is_empty() {
                    self.bucket_map.remove(count);
                }
            });

            // Decrement count and add to the new bucket if count > 0
            *count -= 1;
            if *count > 0 {
                self.bucket_map.entry(*count).or_insert_with(Vec::new).push(key);
            } else {
                // Remove key from count_map if count becomes 0
                self.count_map.remove(&key);
            }
        }
    }

    fn get_max_key(&self) -> String {
        self.bucket_map.iter().rev().next().map(|(_, v)| v[0].clone()).unwrap_or_default()
    }

    fn get_min_key(&self) -> String {
        self.bucket_map.iter().next().map(|(_, v)| v[0].clone()).unwrap_or_default()
    }
}

fn main() {
    // 示例用法
    let mut obj = AllOne::new();
    obj.inc("hello".to_string());
    obj.inc("world".to_string());
    obj.inc("hello".to_string());
    obj.dec("world".to_string());
    let max_key = obj.get_max_key();
    let min_key = obj.get_min_key();

    println!("Max Key: {}", max_key);
    println!("Min Key: {}", min_key);
}

请注意，这只是一个简化的实现，实际应用中可能需要更多的边界检查和处理错误的逻辑。希望这个示例对你在 Rust 中实现类似的功能有所帮助。

文章目录