Design a number container system that can do the following:
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 <= 109105 calls will be made in total to change and find.class NumberContainers {
HashMap<Integer, Integer> container;
HashMap<Integer, PriorityQueue<Integer>> baseIdx;
public NumberContainers() {
container = new HashMap<>();
baseIdx = new HashMap<>();
}
public void change(int index, int number) {
container.put(index, number);
baseIdx.computeIfAbsent(number, k -> new PriorityQueue<>()).offer(index);
}
public int find(int number) {
while (baseIdx.containsKey(number) && !baseIdx.get(number).isEmpty()) {
int i = baseIdx.get(number).peek();
if (container.get(i) == number)
return i;
else
baseIdx.get(number).poll();
}
return -1;
}
}
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers obj = new NumberContainers();
* obj.change(index,number);
* int param_2 = obj.find(number);
*/class NumberContainers {
HashMap<Integer, Integer> container;
HashMap<Integer, TreeSet<Integer>> baseIdx;
public NumberContainers() {
container = new HashMap<>();
baseIdx = new HashMap<>();
}
public void change(int index, int number) {
if (container.containsKey(index))
baseIdx.get(container.get(index)).remove(index);
container.put(index, number);
baseIdx.putIfAbsent(number, new TreeSet<>());
baseIdx.get(number).add(index);
}
public int find(int number) {
if (baseIdx.containsKey(number) && !baseIdx.get(number).isEmpty())
return baseIdx.get(number).first();
return -1;
}
}
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers obj = new NumberContainers();
* obj.change(index,number);
* int param_2 = obj.find(number);
*/class NumberContainers {
HashMap<Integer, Integer> container;
HashMap<Integer, TreeSet<Integer>> baseIdx;
public NumberContainers() {
container = new HashMap<>();
baseIdx = new HashMap<>();
}
public void change(int index, int number) {
if (container.containsKey(index))
baseIdx.get(container.get(index)).remove(index);
container.put(index, number);
baseIdx.putIfAbsent(number, new TreeSet<>());
baseIdx.get(number).add(index);
}
public int find(int number) {
if (baseIdx.containsKey(number) && !baseIdx.get(number).isEmpty())
return baseIdx.get(number).first();
return -1;
}
}
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers obj = new NumberContainers();
* obj.change(index,number);
* int param_2 = obj.find(number);
*/