924. Express Lanes List
A metro line has many stations in a row, and the transit authority wants fast lookups, so it adds express lanes that skip stations. Build the class ExpressLanes (no constructor arguments), a sorted multiset of integers that you may implement with a skiplist or any other structure with the same behaviour.
search(target)returnstrueif at least one copy oftargetis stored.add(num)stores one more copy ofnum; duplicates are allowed.erase(num)removes exactly one copy ofnumand returnstrue; if no copy exists it returnsfalse.
Each operation should take O(log n) expected time.
Example 1
- Input:
- operations = ["ExpressLanes","search","add","add","add","search","search","erase","erase","search"]arguments = [[],[30],[30],[12],[47],[12],[13],[13],[47],[47]]
- Output:
- [null,false,null,null,null,true,false,false,true,false]
- Explanation:
Searching an empty list fails; 13 was never added so erasing it fails; 47 is found, erased once, and then no longer found.
Example 2
- Input:
- operations = ["ExpressLanes","add","add","add","erase","search","erase","erase","search","erase"]arguments = [[],[9],[9],[9],[9],[9],[9],[9],[9],[9]]
- Output:
- [null,null,null,null,true,true,true,true,false,false]
- Explanation:
Three copies of 9 are stored; each erase removes exactly one copy, so the fourth erase fails and search turns false after the third.
Constraints
0 ≤ target, num ≤ 100000
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) expected per call
- Space
- O(n)