跳转至

1429.First Unique Number

Tags: Hash Table Queue Medium

Links: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3313/

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.
class FirstUnique {
    unordered_map<int, list<int>> freq;
    unordered_map<int, list<int>::iterator> it;
    unordered_map<int, int> s;
public:
    FirstUnique(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            add(nums[i]);
        }
    }

    int showFirstUnique() {
        return freq[1].size() == 0 ? -1 : freq[1].back();
    }

    void add(int value) {
        if (s.find(value) == s.end()) {
            freq[1].push_front(value);
            it[value] = freq[1].begin();
            ++s[value];
        }
        else {
            if (s[value] == 1) {
                auto pos = it[value];
                freq[1].erase(pos);
                it.erase(value);
                ++s[value];
            }
            else ++s[value];
        }
    }
};

/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique* obj = new FirstUnique(nums);
 * int param_1 = obj->showFirstUnique();
 * obj->add(value);
 */

这道题是一个设计类型的问题，仅涉及两个操作，一个是查询第一个只出现一次的数，另一个是往序列里增加一个数。“第一个只出现一次”这个条件，其实可以很敏感的联想到LRU和LFU，LRU和LFU传递的很重要的思路是：

  • 如何表示插入顺序的先后？用双向链表来解决，链表靠前位置表示先出现，后来的元素插在尾端（究竟首尾哪一段表示位置靠前可以自行规定）
  • 如何解决链表不能随机访问的缺点？用unordered_map将链表的迭代器和某一查询要素进行映射，以达到O(1)访问的目的。
  • LFU启发的思路是如何处理和频率相关的问题。

那么这道题其实就可以从LRU和LFU中提取思路。用freq这个unordered_map用来建立频率和元素之间的映射，这里之存储频率为1的元素，值是一个链表，链表尾端表示顺序靠前，尾端表示新插入的元素。为了快速访问，用it建立元素和其在链表中迭代器的映射，因为这里之存储频率为1的元素，所以链表也不会出现重复元素。用s记录每个数字出现的频率。

初始化部分，对于第一次出现的元素，插入到freq中的链表，用it记录迭代器的位置，当插入一个元素发现和之前插入的元素重复时，如果之前这个元素只是出现一次，那么说明这个元素目前还在频率为1的链表中，那么就需要把它删掉；如果这个元素的频率超过一次，说明肯定不会在频率为1的链表里，也就无需执行删除操作了。这一部分的内容和LFU非常接近