【LeetCode】设计数字容器系统 Java 题解

作者：Albert

2022 年 8 月 02 日
本文字数：1608 字
阅读完需：约 5 分钟

题目描述

设计一个数字容器系统，可以实现以下功能：

在系统中给定下标处插入或者替换一个数字。返回系统中给定数字的最小下标。请你实现一个 NumberContainers 类：

NumberContainers() 初始化数字容器系统。void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了，那么用 number 替换该数字。int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。

示例：
输入：["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"][[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]输出：[null, -1, null, null, null, null, 1, null, 2]
解释：NumberContainers nc = new NumberContainers();nc.find(10); // 没有数字 10 ，所以返回 -1 。nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/design-a-number-container-system著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的的算法题目是设计类题目。题目描述比较长，我们跟着例子来理解。
题目给出的是设计数字容器，实现 find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。根据这里分析，我们需要实现一个对 number 所在全部下标的排序。由于元素无重复，我们可以使用 TreeSet 来存储。TreeSet 的按照排序顺序来存储元素. 我们也可以通过比较器来精确定义按照什么样的排序顺序。实现 Comparator 方法即可。
change() 方法会修改索引位置元素的值，从而影响 number 的索引排序。因此，我们来使用 indexMap 记录 index 和 map 的关系，在修改的时候，先处理原来的值，在处理新加的值。保证数据的准确行。
具体实现代码如下，供参考。

通过代码

class NumberContainers {    Map<Integer, Integer> indexMap;    Map<Integer, TreeSet<Integer>> map;
    public NumberContainers() {        indexMap = new HashMap<>();        map = new HashMap<>();    }        public void change(int index, int number) {        Integer oldValue = indexMap.getOrDefault(index, - 1);        TreeSet<Integer> set;        if (oldValue != -1) {            set = map.getOrDefault(oldValue, new TreeSet<>());            set.remove(index);            map.put(oldValue, set);        }                set = map.getOrDefault(number, new TreeSet<>());        set.add(index);        map.put(number, set);
        indexMap.put(index, number);    }        public int find(int number) {        int ans = -1;        TreeSet<Integer> set = map.getOrDefault(number, new TreeSet<>());        if (set.size() == 0) {            return ans;        }        ans = set.first();        return ans;    }}