Description#
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.
Solutions#
Solution 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
| from sortedcontainers import SortedSet
class NumberContainers:
def __init__(self):
self.mp = {}
self.t = defaultdict(SortedSet)
def change(self, index: int, number: int) -> None:
if index in self.mp:
v = self.mp[index]
self.t[v].remove(index)
self.mp[index] = number
self.t[number].add(index)
def find(self, number: int) -> int:
s = self.t[number]
return s[0] if s else -1
# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
|
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
| class NumberContainers {
private Map<Integer, Integer> mp = new HashMap<>();
private Map<Integer, TreeSet<Integer>> t = new HashMap<>();
public NumberContainers() {
}
public void change(int index, int number) {
if (mp.containsKey(index)) {
int v = mp.get(index);
t.get(v).remove(index);
if (t.get(v).isEmpty()) {
t.remove(v);
}
}
mp.put(index, number);
t.computeIfAbsent(number, k -> new TreeSet<>()).add(index);
}
public int find(int number) {
return t.containsKey(number) ? t.get(number).first() : -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);
*/
|
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
| class NumberContainers {
public:
map<int, int> mp;
map<int, set<int>> t;
NumberContainers() {
}
void change(int index, int number) {
auto it = mp.find(index);
if (it != mp.end()) {
t[it->second].erase(index);
it->second = number;
} else
mp[index] = number;
t[number].insert(index);
}
int find(int number) {
auto it = t.find(number);
return it == t.end() || it->second.empty() ? -1 : *it->second.begin();
}
};
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers* obj = new NumberContainers();
* obj->change(index,number);
* int param_2 = obj->find(number);
*/
|
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
| type NumberContainers struct {
mp map[int]int
t map[int]*redblacktree.Tree
}
func Constructor() NumberContainers {
return NumberContainers{map[int]int{}, map[int]*redblacktree.Tree{}}
}
func (this *NumberContainers) Change(index int, number int) {
if num, ok := this.mp[index]; ok {
this.t[num].Remove(index)
}
this.mp[index] = number
if this.t[number] == nil {
this.t[number] = redblacktree.NewWithIntComparator()
}
this.t[number].Put(index, nil)
}
func (this *NumberContainers) Find(number int) int {
s, ok := this.t[number]
if !ok || s.Size() == 0 {
return -1
}
return s.Left().Key.(int)
}
/**
* Your NumberContainers object will be instantiated and called as such:
* obj := Constructor();
* obj.Change(index,number);
* param_2 := obj.Find(number);
*/
|
