922. Number Lockers
A storage hall has a huge number of numbered lockers, each able to hold one integer; lockers are identified by an index and start empty. Write the class NumberLockers (no constructor arguments).
change(index, number)putsnumberinto lockerindex, replacing whatever it held before.find(number)returns the smallest index of a locker that currently holdsnumber, or -1 if no locker does.
Indices can be as large as 10^9, so you cannot allocate all lockers. Both operations should run in O(log n) amortized time, where n is the number of calls so far; scanning every used locker on each find is too slow for the intended solution.
Example 1
- Input:
- operations = ["NumberLockers","find","change","change","find","change","find","find","change","find","find"]arguments = [[],[5],[40,5],[12,5],[5],[12,8],[5],[8],[40,8],[5],[8]]
- Output:
- [null,-1,null,null,12,null,40,12,null,-1,12]
- Explanation:
Locker 12 holds 5 until it is overwritten with 8; then only locker 40 holds 5, and once 40 also becomes 8, no locker holds 5, while 12 is the smallest holding 8.
Example 2
- Input:
- operations = ["NumberLockers","change","change","change","find","change","find","find"]arguments = [[],[1000000000,3],[7,3],[7,3],[3],[7,4],[3],[4]]
- Output:
- [null,null,null,null,7,null,1000000000,7]
- Explanation:
Writing the same number into a locker again is harmless; after locker 7 changes to 4 the smallest index with 3 is 1000000000.
Constraints
1 ≤ index, number ≤ 109
At most 3000 calls in total
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n) amortized per call
- Space
- O(n)