[LeetCode] 2349. Design a Number Container System

Design a number container system that can do the following:
Insert or Replace a number at the given index in the system.
Return the smallest index for the given number in the system.

Implement the NumberContainers class:
NumberContainers() Initializes the number container system.
void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

Example 1:
Input
[“NumberContainers”, “find”, “change”, “change”, “change”, “change”, “find”, “change”, “find”]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]

Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20.
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

Constraints:
1 <= index, number <= 109
At most 105 calls will be made in total to change and find.

设计数字容器系统。

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

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

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

思路

创建两个hashmap，第一个存储index和number的映射，第二个存储number和index的映射。其中第二个hashmap里是<number, TreeSet>，因为存的是当前这个数字所有出现过的下标。为什么要用TreeSet存是因为需要很快找到最小的index和删除index，TreeSet里，删除这个动作的时间复杂度是O(logn)。

复杂度

• change函数
  时间O(nlogn)
  空间O(n)

• find函数
  时间O(1)
  空间O(1)

代码

Java实现

class NumberContainers {
    // <index, number>
    HashMap<Integer, Integer> indexMap = new HashMap<>();
    // <number, set of indexes>
    HashMap<Integer, TreeSet<Integer>> numberMap = new HashMap<>();

    public NumberContainers() {

    }

    public void change(int index, int number) {
        if (indexMap.containsKey(index)) {
            int oldNumber = indexMap.get(index);
            numberMap.get(oldNumber).remove(index);
        }
        indexMap.put(index, number);
        if (!numberMap.containsKey(number)) {
            numberMap.put(number, new TreeSet<>());
        }
        numberMap.get(number).add(index);
    }

    public int find(int number) {
        int min = Integer.MAX_VALUE;
        if (numberMap.containsKey(number)) {
            TreeSet<Integer> indexes = numberMap.get(number);
            if (indexes.size() > 0) {
                return indexes.first();
            } else {
                return -1;
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers obj = new NumberContainers();
 * obj.change(index,number);
 * int param_2 = obj.find(number);
 */