Description#
You have a queue of integers, you need to retrieve the first unique integer in the queue.
Implement the FirstUnique class:
FirstUnique(int[] nums) Initializes the object with the numbers in the queue.int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.void add(int value) insert value to the queue.
Example 1:
Input:
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5); // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1
Example 2:
Input:
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:
[null,-1,null,null,null,null,null,17]
Explanation:
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17); // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17
Example 3:
Input:
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output:
[null,809,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809); // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^81 <= value <= 10^8- At most
50000 calls will be made to showFirstUnique and add.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class FirstUnique:
def __init__(self, nums: List[int]):
self.cnt = Counter(nums)
self.unique = OrderedDict({v: 1 for v in nums if self.cnt[v] == 1})
def showFirstUnique(self) -> int:
return -1 if not self.unique else next(v for v in self.unique.keys())
def add(self, value: int) -> None:
self.cnt[value] += 1
if self.cnt[value] == 1:
self.unique[value] = 1
elif value in self.unique:
self.unique.pop(value)
# Your FirstUnique object will be instantiated and called as such:
# obj = FirstUnique(nums)
# param_1 = obj.showFirstUnique()
# obj.add(value)
|
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
35
| class FirstUnique {
private Map<Integer, Integer> cnt = new HashMap<>();
private Set<Integer> unique = new LinkedHashSet<>();
public FirstUnique(int[] nums) {
for (int v : nums) {
cnt.put(v, cnt.getOrDefault(v, 0) + 1);
}
for (int v : nums) {
if (cnt.get(v) == 1) {
unique.add(v);
}
}
}
public int showFirstUnique() {
return unique.isEmpty() ? -1 : unique.iterator().next();
}
public void add(int value) {
cnt.put(value, cnt.getOrDefault(value, 0) + 1);
if (cnt.get(value) == 1) {
unique.add(value);
} else {
unique.remove(value);
}
}
}
/**
* Your FirstUnique object will be instantiated and called as such:
* FirstUnique obj = new FirstUnique(nums);
* int param_1 = obj.showFirstUnique();
* obj.add(value);
*/
|
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 FirstUnique {
public:
FirstUnique(vector<int>& nums) {
for (int& v : nums) {
++cnt[v];
q.push_back(v);
}
}
int showFirstUnique() {
while (q.size() && cnt[q.front()] != 1) q.pop_front();
return q.size() ? q.front() : -1;
}
void add(int value) {
++cnt[value];
q.push_back(value);
}
private:
unordered_map<int, int> cnt;
deque<int> q;
};
/**
* Your FirstUnique object will be instantiated and called as such:
* FirstUnique* obj = new FirstUnique(nums);
* int param_1 = obj->showFirstUnique();
* obj->add(value);
*/
|
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 FirstUnique struct {
cnt map[int]int
q []int
}
func Constructor(nums []int) FirstUnique {
cnt := map[int]int{}
for _, v := range nums {
cnt[v]++
}
return FirstUnique{cnt, nums}
}
func (this *FirstUnique) ShowFirstUnique() int {
for len(this.q) > 0 && this.cnt[this.q[0]] != 1 {
this.q = this.q[1:]
}
if len(this.q) > 0 {
return this.q[0]
}
return -1
}
func (this *FirstUnique) Add(value int) {
this.cnt[value]++
this.q = append(this.q, value)
}
/**
* Your FirstUnique object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.ShowFirstUnique();
* obj.Add(value);
*/
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class FirstUnique:
def __init__(self, nums: List[int]):
self.cnt = Counter(nums)
self.q = deque(nums)
def showFirstUnique(self) -> int:
while self.q and self.cnt[self.q[0]] != 1:
self.q.popleft()
return -1 if not self.q else self.q[0]
def add(self, value: int) -> None:
self.cnt[value] += 1
self.q.append(value)
# Your FirstUnique object will be instantiated and called as such:
# obj = FirstUnique(nums)
# param_1 = obj.showFirstUnique()
# obj.add(value)
|
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 FirstUnique {
private Map<Integer, Integer> cnt = new HashMap<>();
private Deque<Integer> q = new ArrayDeque<>();
public FirstUnique(int[] nums) {
for (int v : nums) {
cnt.put(v, cnt.getOrDefault(v, 0) + 1);
q.offer(v);
}
}
public int showFirstUnique() {
while (!q.isEmpty() && cnt.get(q.peekFirst()) != 1) {
q.poll();
}
return q.isEmpty() ? -1 : q.peekFirst();
}
public void add(int value) {
cnt.put(value, cnt.getOrDefault(value, 0) + 1);
q.offer(value);
}
}
/**
* Your FirstUnique object will be instantiated and called as such:
* FirstUnique obj = new FirstUnique(nums);
* int param_1 = obj.showFirstUnique();
* obj.add(value);
*/
|
