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.

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^5
• 1 <= nums[i] <= 10^8
• 1 <= value <= 10^8
• At most 50000 calls will be made to showFirstUnique and add.

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1429

解题思路分析：

这道题主要考察的是数据存储结构，我们需要掌握全部数字的信息，以及唯一数字的信息，这两点信息我们可以使用两个Set来存储。使用Set的原因是set本身在查看是否存在重复数字时的时间复杂度是1，强于ArrayList以及数组等其他集合。

解题时，我们新建两个Set，一个用来存储所有的数字（allSet），另一个Set用来存储只出现过一次的数字（uniqueSet）。由于题目要求返回第一个只出现过一次的数字，所以Set中存储的数据需要保持一定的顺序才可以，因此这里我们采用LinkedHashSet来存储。

在add方法中，我们首先判断allSet中是否存在当前要加入的数字，如果存在的话，说明当前数字不再是唯一数，我们从uniqueSet中删除该数字。反之如果allSet中不存在该数字的话，我们将该数字分别加入allSet和uniqueSet中。

showFirstUnique方法中，因为uniqueSet保存的是所有唯一数，并且该集合已经按照输入的顺序排序好，因此只要返回uniqueSet中的首元素即可。另外当uniqueSet的元素个数为0的话，返回-1。

实现代码：

Set<Integer> all = new HashSet<>(); // 存储所有数字
Set<Integer> unique = new LinkedHashSet<>(); // 只存储唯一数
public FirstUnique(int[] nums) {
    for(int n : nums){ // 循环每一个数字
        if(all.contains(n)){ // 如果all中包含该数字
            // 该数字不是唯一数，将其从unique中删除
            unique.remove(n);
        }else{ // 如果all中不包含该数字
            all.add(n); // 将其添加至all
            unique.add(n); // 将其添加至unique
        }
    }
}

public int showFirstUnique() {
    if(unique.size()>0){ // 返回unique中首元素
        return unique.iterator().next();
    }
    return -1;
}

public void add(int value) {
    // 与构造函数逻辑相同
    if(all.contains(value)){
        unique.remove(value);
    }else{
        all.add(value);
        unique.add(value);
    }
}

本题解法执行时间为123ms。

Runtime: 123 ms, faster than 40.32% of Java online submissions for First Unique Number.

Memory Usage: 84.5 MB, less than 100.00% of Java online submissions for First Unique Number.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1429-first-unique-number-解题思路分析/