双端链表的作用

之前在做LRU这道题时，用到了双端链表，今天在完成Leetcode的每日一题时，发现利用双端链表可以完成解答。

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.

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

class FirstUnique {
public:
    struct Node{
        int val;
        Node *prev;
        Node *next;
        Node(int value): val(value), prev(NULL), next(NULL){};
    };
    map<int, Node*>unique;
    set<int>store;
    Node *begin;
    Node *end;
    FirstUnique(vector<int>& nums) {
        begin = new Node(-1);
        end = new Node(-1);
        begin->next = end;
        end->prev = begin;
        for(auto &index : nums)
        {
            if(store.find(index) == store.end())
            {
                Node *cur = new Node(index);
                unique[index] = cur;
                Node *pre = end->prev;
                pre->next = cur;
                cur->prev = pre;
                cur->next = end;
                end->prev = cur;
                store.insert(index);
            }
            else
            {
                if(unique.find(index) != unique.end())
                {
                    Node *cur = unique[index];
                    unique.erase(index);
                    Node *pre = cur->prev;
                    Node *nex = cur->next;
                    pre->next = nex;
                    nex->prev = pre;
                    delete cur;
                }
            }
        }
    }
    int showFirstUnique() {
        if(!unique.empty())
            return begin->next->val;
        else
            return -1;
    }
    void add(int value) {
        if(store.find(value) == store.end())
            {
                Node *cur = new Node(value);
                unique[value] = cur;
                Node *pre = end->prev;
                pre->next = cur;
                cur->prev = pre;
                cur->next = end;
                end->prev = cur;
                store.insert(value);
            }
            else
            {
                if(unique.find(value) != unique.end())
                {
                    Node *cur = unique[value];
                    unique.erase(value);
                    Node *pre = cur->prev;
                    Node *nex = cur->next;
                    pre->next = nex;
                    nex->prev = pre;
                    delete cur;
                }
            }
    }
};
/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique* obj = new FirstUnique(nums);
 * int param_1 = obj->showFirstUnique();
 * obj->add(value);
 */

提交的结果如下，貌似占用了很大的内存。

题目总共提供了三种思路，双端链表是其中最容易想到的一种思路

Note1: Use doubly Linked list with hashmap of pointers to linked list nodes. add unique number to the linked list. When add is called check if the added number is unique then it have to be added to the linked list and if it is repeated remove it from the linked list if exists. When showFirstUnique is called retrieve the head of the linked list.

Note2: Use queue and check that first element of the queue is always unique.

Note3: Use set or heap to make running time of each function O(logn).