<div>
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:
<pre>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 </pre>
Example 2:
<pre>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 </pre>
Example 3:
<pre>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 </pre>
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^81 <= value <= 10^8- At most
50000calls will be made toshowFirstUniqueandadd.
</div>
算法思路：
Dict + LL (1次) + Set (2次)。此题非常类似于LRU, 相当于实习LinkedHashMap。
由易到难
| 题目 | LL | Map | 其他数据结构 |
|---|---|---|---|
| LRU | 按时间顺序，头删尾入 | 值->LL节点 | N/A |
| First Unique | 按时间顺序，任意删尾入 | 值->LL节点 | Set存两次以上 |
| LFU | 多个时间顺序的LL | 值->LL节点 | 第二个Map存freq-> LL的首节点以及min_freq |
注意事项：
- 注意两种情况，节点不在Map, 在Map中，对应的LL操作同样是add_to_tail和remove_node不过少了move_to_tail。
- 头尾dummy node，初始化要相连。
- 注意删除顺序，先删map中的entry再删Node。否则会出现NPE。新加入是顺序相反。删除节点要将prev和next赋None
- 区别还有ListNode不需要key，因为输入是单值，不是key-value对。数据结构多了set来记录出现两次及以上的元素，直接忽略
Python代码：
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65class FirstUnique(TestCases):
'''
2, 3, 5, 5
dict:
{2:1
3:1
5:2 (remove)
}
LinkedList: 2, 3, 5(r), 5(r)
dict:
{
2: Node(2)
3: Node(3)
5: Node(5)
}
'''
def __init__(self, nums: List[int]):
self.head = ListNode(0) # only store unique elements
self.tail = ListNode(0)
self.key_to_node = {} # only store unique elements
self.non_unique_set = set()
self.head.next, self.tail.prev = self.tail, self.head
for n in nums:
self.add(n)
def showFirstUnique(self) -> int:
if len(self.key_to_node) == 0:
return -1
return self.head.next.val
# 2, 3, 5, 5
def add(self, value: int) -> None:
if value in self.non_unique_set:
return
if value not in self.key_to_node:
new_node = ListNode(value)
self.add_to_tail(new_node)
self.key_to_node[value] = new_node
else:
to_be_removed_node = self.key_to_node[value]
self.key_to_node.pop(value)
self.remove_node(to_be_removed_node)
self.non_unique_set.add(value)
def add_to_tail(self, node):
predecessor = self.tail.prev
predecessor.next, node.prev = node, predecessor
node.next, self.tail.prev = self.tail, node
def remove_node(self, node):
predecessor, successor = node.prev, node.next
predecessor.next, successor.prev = successor, predecessor
node.prev, node.next = None, None
class ListNode:
def __init__(self, val, next = None, prev = None):
self.val = val
self.next = next
self.prev = prev
算法分析：
每个操作时间复杂度为O(1)，空间复杂度O(n).
