Karl's Nest
0%

leetcode-day-28

Posted on In
Day-28 First Unique Number

LeetCode 30 days Challenge - Day 28

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

1
2
3
4
5
6
7
8
9
10
11
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.

Solution

题目要求分析：实现一个能够返回第一个唯一元素的队列。要求实现：1.返回第一个唯一元素的功能；2. 添加一个新元素。

解法：

本题重点需要理清，两个功能在各种不同的情况下，应该如何工作：

  1. showFirstUnique()：
    1. 当队列为空，或没有唯一元素，返回 -1；
    2. 当队列存在唯一元素，返回第一个唯一的元素值。
  2. add(int value)：
    1. 当队列不存在该元素，那么加入队列。
    2. 当队列存在该元素，那么将原来的元素从队列中移除，并且以后不能在加入该元素。

到这里，逻辑思路就整理完毕，接下来考虑数据结构使用问题。

  1. 为了常量时间访存，使用存在头尾指针的双向链表来存储唯一的元素：
    1. 每个元素初次出现都加入该链表，当重复的元素出现时，从该表移除，且不再加入该表，所以说存储的是“唯一的”元素。
    2. 第一个唯一元素即为第一个链表元素：head->next == rear ? -1 : head->next->val；此处注意对链表是否为空的判断。
    3. 当通过add加入新元素：新元素通过尾插法加入链表，不会打乱原有的相对顺序。
    4. 当出现重复元素，删除某一节点时：参见代码removeNode(ListNode* node)处。
  2. 为了常量时间判断元素存在，建立从value到链表指针的映射unordered_map<int, ListNode*> m：
    1. 添加一个元素时，通过 m.find(value) != m.end()判断元素是否存在。
    2. 若不存在，新建链表结点、插入链表中、将指针赋给m[value]，这样可以通过常量时间访问到该value对应的链表结点。
    3. 为了实现“以后不能在加入该元素”的功能，当出现重复元素时，从链表中删除原元素后，将m[value]指向NULL，未来再次遇到该元素时就不会再次进行删除元素操作（已经不存在该元素，删除操作会造成错误）。

本题值得细品，勿只读解法，务必参考代码，整理清楚逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class FirstUnique {
public:
    struct ListNode {
        int val;
        ListNode* pre;
        ListNode* next;
        ListNode(int x) : val(x), pre(NULL), next(NULL) {}
    };

    ListNode* addNode(int val) {
        ListNode* node = new ListNode(val);
        rear->pre->next = node;
        node->pre = rear->pre;
        node->next = rear;
        rear->pre = node;
        return node;
    }

    void removeNode(ListNode* node) {
        ListNode* tmp = node;
        node->next->pre = node->pre;
        node->pre->next = node->next;
        delete tmp;
    }

    ListNode* head = new ListNode(0);
    ListNode* rear = new ListNode(0);
    unordered_map<int, ListNode*> m;

    FirstUnique(vector<int>& nums) {
        head->next = rear;
        rear->pre = head;
        for (int i : nums) add(i);
    }

    int showFirstUnique() {
        return head->next == rear ? -1 : head->next->val;
    }

    void add(int value) {
        if (m.find(value) != m.end()) {
            if (m[value] != NULL) {
                removeNode(m[value]);
                m[value] = NULL;
            }
        }
        else if (m.find(value) == m.end()) {
            ListNode* node = addNode(value);
            m[value] = node;
        }
    }
};

传送门：First Unique Number

Karl