队列｜ Leetcode 1429

Leetcode 分类刷题 —— 队列（Queue）

1、题目描述：

Leetcode 1429. First Unique Number 第一个唯一数字

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.

给定一系列整数，插入一个队列中，找出队列中第一个唯一整数。
实现 FirstUnique 类：
FirstUnique(int[] nums) 用数组里的数字初始化队列。
int showFirstUnique() 返回队列中的第一个唯一整数的值。如果没有唯一整数，返回 -1。
void add(int value) 将 value 插入队列中。

2、示例：

示例 1：
输入：
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
输出：
[null,2,null,2,null,3,null,-1]
解释：
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // 返回 2
firstUnique.add(5);            // 此时队列为 [2,3,5,5]
firstUnique.showFirstUnique(); // 返回 2
firstUnique.add(2);            // 此时队列为 [2,3,5,5,2]
firstUnique.showFirstUnique(); // 返回 3
firstUnique.add(3);            // 此时队列为 [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // 返回 -1

3、解题思路：

使用map+queue：
map 计数，记录每个数字的大小和出现的次数；
queue 维护数字的顺序，队列中计数 > 1 的元素会被全部移除。

4、代码：

import java.util.*;

/**
 * @author ChatGPT
 * @date 2022/3/20
 */
class FirstUnique {
    private Queue<Integer> queue;
    private Map<Integer,  Integer> countMap;

    public FirstUnique(int[] nums){
        queue = new LinkedList<>();
        countMap = new HashMap<>();
        for (int value : nums) {
            add(value);
        }
    }

    public void add(int value){
        countMap.put(value, countMap.getOrDefault(value, 0) + 1);
        queue.offer(value);
    }

    public int showFirstUnique() {
        while (!queue.isEmpty() && countMap.get(queue.peek()) > 1){
            queue.poll();
        }
        if(queue.isEmpty()){
            return -1;
        }else{
            return queue.peek();
        }
    }
}