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 9101112131415161718192021222324
fromsortedcontainersimportSortedSetclassNumberContainers:def__init__(self):self.mp={}self.t=defaultdict(SortedSet)defchange(self,index:int,number:int)->None:ifindexinself.mp:v=self.mp[index]self.t[v].remove(index)self.mp[index]=numberself.t[number].add(index)deffind(self,number:int)->int:s=self.t[number]returns[0]ifselse-1# Your NumberContainers object will be instantiated and called as such:# obj = NumberContainers()# obj.change(index,number)# param_2 = obj.find(number)
classNumberContainers{privateMap<Integer,Integer>mp=newHashMap<>();privateMap<Integer,TreeSet<Integer>>t=newHashMap<>();publicNumberContainers(){}publicvoidchange(intindex,intnumber){if(mp.containsKey(index)){intv=mp.get(index);t.get(v).remove(index);if(t.get(v).isEmpty()){t.remove(v);}}mp.put(index,number);t.computeIfAbsent(number,k->newTreeSet<>()).add(index);}publicintfind(intnumber){returnt.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); */
classNumberContainers{public:map<int,int>mp;map<int,set<int>>t;NumberContainers(){}voidchange(intindex,intnumber){autoit=mp.find(index);if(it!=mp.end()){t[it->second].erase(index);it->second=number;}elsemp[index]=number;t[number].insert(index);}intfind(intnumber){autoit=t.find(number);returnit==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); */
typeNumberContainersstruct{mpmap[int]inttmap[int]*redblacktree.Tree}funcConstructor()NumberContainers{returnNumberContainers{map[int]int{},map[int]*redblacktree.Tree{}}}func(this*NumberContainers)Change(indexint,numberint){ifnum,ok:=this.mp[index];ok{this.t[num].Remove(index)}this.mp[index]=numberifthis.t[number]==nil{this.t[number]=redblacktree.NewWithIntComparator()}this.t[number].Put(index,nil)}func(this*NumberContainers)Find(numberint)int{s,ok:=this.t[number]if!ok||s.Size()==0{return-1}returns.Left().Key.(int)}/** * Your NumberContainers object will be instantiated and called as such: * obj := Constructor(); * obj.Change(index,number); * param_2 := obj.Find(number); */