448. First Unique in Stream
A lottery machine keeps drawing numbered balls, and between draws an announcer wants to name the earliest drawn number that has appeared exactly once so far. A number that shows up again stops being a candidate forever, even if it was the first one drawn.
Implement FirstUnique. The constructor receives an array nums with the numbers drawn so far, in order. showFirstUnique() returns the value that was drawn earliest among those occurring exactly once in everything drawn so far, or -1 if no such value exists. add(value) records one more drawn number at the end of the stream.
Example 1
- Input:
- operations = ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]arguments = [[[6,3,6,9]],[],[3],[],[9],[],[2],[]]
- Output:
- [null,3,null,9,null,-1,null,2]
- Explanation:
Initially 3 and 9 occur once and 3 came first. After adding another 3 only 9 is unique; after another 9 nothing is unique (-1); adding 2 makes 2 the only unique value.
Example 2
- Input:
- operations = ["FirstUnique","showFirstUnique","add","add","showFirstUnique","add","showFirstUnique"]arguments = [[[]],[],[14],[11],[],[14],[]]
- Output:
- [null,-1,null,null,14,null,11]
- Explanation:
With nothing drawn the result is -1. After drawing 14 and 11 the first unique is 14, but a second 14 removes it and 11 takes over.
Constraints
0 ≤ nums.length ≤ 105
1 ≤ nums[i], value ≤ 108
At most 5 * 104 calls to showFirstUnique and add.
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(1) amortized per operation
- Space
- O(n)