第一个唯一数字

题目(LeetCode #1429)

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

题解

方法一：可以使用队列保存输入的所有数字，并创建一个 Map 来保存各数字的出现次数，执行 add 时直接将新元素添加至队尾；执行 firstUnique 时从队首逐个判断是否唯一，若不唯一则弹出该元素，直到找到第一个唯一的元素为止。这种方法时间和空间复杂度都是 O(n)，可能需要弹出很多元素才能找到结果。

方法二：创建一个队列保存输入的数字，并使用一个 Set 保存所有数字，添加元素时先判断该数字是否已经出现过，若出现过则从队列中移除该元素。时间和空间复杂度仍都为 O(n)，firstUnique 操作的时间复杂度降为 O(1)，但 add 操作最坏情况下仍为 O(n)。该解法中的队列可改用 LinkedHashSet，进一步降低 add 时移除重复元素的复杂度。

class FirstUnique {
    Set<Integer> unique = new LinkedHashSet<>();
    Set<Integer> all = new HashSet<>();

    public FirstUnique(int[] nums) {
        for (int num : nums) add(num);
    }

    public void add(int num) {
        if (all.add(num)) unique.add(num);
        else unique.remove(num);
    }

    public int showFirstUnique() {
        return unique.isEmpty() ? -1 : unique.iterator().next();
    }
}