LeetCode题练习与总结：全 O(1) 的数据结构--432

一直学习永不止步

1796人浏览 · 2024-11-28 15:00:00

一直学习永不止步 · 2024-11-28 15:00:00 发布

一、题目描述

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

实现 AllOne 类：

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

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

示例：

输入
["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"

提示：

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

二、解题思路

数据结构设计：
- 使用两个哈希表countMap和valueMap来存储字符串及其对应的计数，以及计数与对应字符串集合的映射关系。
- countMap：键为字符串，值为该字符串的计数。
- valueMap：键为计数，值为具有该计数的字符串集合。
初始化：
- 在构造函数中初始化countMap和valueMap。
增加计数（inc）：
- 首先从countMap中获取当前字符串的计数，如果不存在则默认为0。
- 将计数加1后更新countMap。
- 如果原计数大于0，则从valueMap中对应的计数集合中移除该字符串。如果移除后集合为空，则删除该计数键。
- 将字符串添加到新的计数集合中，如果该计数集合不存在，则创建一个新的集合。
减少计数（dec）：
- 从countMap中获取当前字符串的计数。
- 如果计数为1，则直接从countMap和valueMap中移除该字符串。
- 如果计数大于1，则将计数减1后更新countMap，并从原计数集合中移除该字符串。如果移除后集合为空，则删除该计数键。
- 将字符串添加到新的计数集合中，如果该计数集合不存在，则创建一个新的集合。
获取最大计数字符串（getMaxKey）：
- 如果valueMap为空，则返回空字符串。
- 使用流操作找到最大的计数，并从对应的字符串集合中返回任意一个字符串。
获取最小计数字符串（getMinKey）：
- 如果valueMap为空，则返回空字符串。
- 使用流操作找到最小的计数，并从对应的字符串集合中返回任意一个字符串。

三、具体代码

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class AllOne {
    private Map<String, Integer> countMap;
    private Map<Integer, Set<String>> valueMap;

    public AllOne() {
        countMap = new HashMap<>();
        valueMap = new HashMap<>();
    }
    
    public void inc(String key) {
        int count = countMap.getOrDefault(key, 0);
        countMap.put(key, count + 1);
        if (count > 0) {
            valueMap.get(count).remove(key);
            if (valueMap.get(count).isEmpty()) {
                valueMap.remove(count);
            }
        }
        valueMap.computeIfAbsent(count + 1, k -> new HashSet<>()).add(key);
    }
    
    public void dec(String key) {
        int count = countMap.get(key);
        if (count == 1) {
            countMap.remove(key);
            valueMap.get(1).remove(key);
            if (valueMap.get(1).isEmpty()) {
                valueMap.remove(1);
            }
        } else {
            countMap.put(key, count - 1);
            valueMap.get(count).remove(key);
            if (valueMap.get(count).isEmpty()) {
                valueMap.remove(count);
            }
            valueMap.computeIfAbsent(count - 1, k -> new HashSet<>()).add(key);
        }
    }
    
    public String getMaxKey() {
        if (valueMap.isEmpty()) return "";
        int maxCount = valueMap.keySet().stream().max(Integer::compare).get();
        return valueMap.get(maxCount).iterator().next();
    }
    
    public String getMinKey() {
        if (valueMap.isEmpty()) return "";
        int minCount = valueMap.keySet().stream().min(Integer::compare).get();
        return valueMap.get(minCount).iterator().next();
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

AllOne() 构造函数：
- 初始化两个哈希表的时间复杂度是 O(1)。
inc(String key) 方法：
- countMap.getOrDefault(key, 0)：获取字符串的当前计数，时间复杂度是 O(1)。
- countMap.put(key, count + 1)：更新字符串的计数，时间复杂度是 O(1)。
- valueMap.get(count).remove(key)：从原计数集合中移除字符串，时间复杂度是 O(1)。
- valueMap.remove(count)：如果集合为空，则删除该计数键，时间复杂度是 O(1)。
- valueMap.computeIfAbsent(count + 1, k -> new HashSet<>()).add(key)：将字符串添加到新的计数集合中，时间复杂度是 O(1)。
- 综上，inc 方法的时间复杂度是 O(1)。
dec(String key) 方法：
- countMap.get(key)：获取字符串的当前计数，时间复杂度是 O(1)。
- countMap.remove(key)：如果计数为1，则从countMap中移除字符串，时间复杂度是 O(1)。
- valueMap.get(1).remove(key)：从计数为1的集合中移除字符串，时间复杂度是 O(1)。
- valueMap.remove(1)：如果集合为空，则删除该计数键，时间复杂度是 O(1)。
- countMap.put(key, count - 1)：更新字符串的计数，时间复杂度是 O(1)。
- valueMap.get(count).remove(key)：从原计数集合中移除字符串，时间复杂度是 O(1)。
- valueMap.remove(count)：如果集合为空，则删除该计数键，时间复杂度是 O(1)。
- valueMap.computeIfAbsent(count - 1, k -> new HashSet<>()).add(key)：将字符串添加到新的计数集合中，时间复杂度是 O(1)。
- 综上，dec 方法的时间复杂度是 O(1)。
getMaxKey() 方法：
- valueMap.keySet().stream().max(Integer::compare).get()：获取最大的计数，时间复杂度是 O(n)，其中 n 是valueMap中不同计数的数量。
- valueMap.get(maxCount).iterator().next()：从最大计数的集合中获取一个字符串，时间复杂度是 O(1)。
- 综上，getMaxKey 方法的时间复杂度是 O(n)。
getMinKey() 方法：
- valueMap.keySet().stream().min(Integer::compare).get()：获取最小的计数，时间复杂度是 O(n)，其中 n 是valueMap中不同计数的数量。
- valueMap.get(minCount).iterator().next()：从最小计数的集合中获取一个字符串，时间复杂度是 O(1)。
- 综上，getMinKey 方法的时间复杂度是 O(n)。

2. 空间复杂度

countMap 哈希表存储了所有字符串及其对应的计数，空间复杂度是 O(m)，其中 m 是字符串的数量。
valueMap 哈希表存储了计数与对应字符串集合的映射关系，空间复杂度是 O(m)，因为每个字符串都会在某个计数字典中。

综合来看，整个数据结构的空间复杂度是 O(m)，即与存储的字符串数量成线性关系。

五、总结知识点

Java 类的定义：
- 如何定义一个类AllOne，包括成员变量和成员方法。
Java 集合框架：
- 使用HashMap来存储键值对，其中countMap存储字符串与其计数的映射，valueMap存储计数与字符串集合的映射。
- 使用HashSet来存储每个计数对应的字符串集合，确保每个字符串在每个计数下是唯一的。
Java 构造函数：
- 如何定义和使用构造函数来初始化类的成员变量。
Java 方法：
- 如何定义和使用类的方法，包括增加计数inc、减少计数dec、获取最大计数字符串getMaxKey和获取最小计数字符串getMinKey。
HashMap 方法：
- getOrDefault：获取指定键对应的值，如果不存在则返回默认值。
- put：向哈希表中插入或更新键值对。
- remove：从哈希表中移除指定的键值对。
- computeIfAbsent：如果指定的键尚未与值关联（或映射到 null），则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非 null。
HashSet 方法：
- add：向集合中添加元素。
- remove：从集合中移除元素。
- iterator：获取集合的迭代器，用于遍历集合中的元素。
Java 流操作：
- 使用stream()方法创建流，然后使用max和min方法来找到集合中的最大值和最小值。
Java 迭代器：
- 使用iterator()方法获取集合的迭代器，并使用next()方法获取迭代器中的下一个元素。
异常处理：
- 在getMaxKey和getMinKey方法中，如果valueMap为空，则返回空字符串，这避免了在空集合上调用max或min方法时抛出异常。
逻辑判断：
- 在inc和dec方法中，使用条件语句来检查字符串的计数是否需要更新或删除。