First Unique Number

Question

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

LeetCodeleetcode.com/problems/first-unique-number

Solution

/*
Algorithm: 一个map查重，一个queue取firstUnique
*/
Queue<Integer> queue;
Map<Integer, Boolean> map;
public FirstUnique(int[] nums) {
    queue = new LinkedList<>();
    map = new HashMap<>();
    for (int n : nums) add(n);
}

public int showFirstUnique() {
    while (!queue.isEmpty() && !map.get(queue.peek())) {
        queue.poll();
    }
    return queue.size() > 0 ? queue.peek() : -1;
}

public void add(int value) {
    if (!map.containsKey(value)) {
        queue.add(value);
        map.put(value, true);
    }else {
        map.put(value, false);
    }
}