How to Design a First Unique Number Class with O(1)?
- 时间:2020-09-09 14:04:20
- 分类:网络文摘
- 阅读:93 次
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:
1 2 ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]]["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]]Output:
[null,2,null,2,null,3,null,-1]Explanation:
1 2 3 4 5 6 7 8 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 -1FirstUnique 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 -1Example 2:
Input:
1 2 ["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"] [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]["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:
1 2 3 4 5 6 7 8 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 17FirstUnique 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 17Example 3:
Input:
1 2 ["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]]["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]]Output:
[null,809,null,-1]Explanation:
1 2 3 4 FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8
1 <= value <= 10^8At most 50000 calls will be made to showFirstUnique and add.
Hints:
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.
Use queue and check that first element of the queue is always unique.
Use set or heap to make running time of each function O(logn).
1 2 3 4 | // Your FirstUnique object will be instantiated and called as such: FirstUnique* obj = new FirstUnique(nums); int param_1 = obj->showFirstUnique(); obj->add(value); |
// Your FirstUnique object will be instantiated and called as such: FirstUnique* obj = new FirstUnique(nums); int param_1 = obj->showFirstUnique(); obj->add(value);
First Unique Number using Double-Linked Queue and Hash Map
The key to design a O(1) data structure which allows to retrieve the first unqiue number and add a number to the queue is to use a double linked list and a hash map.
The elements in the double linked list are always unique. And the hash map allows us to retrieve a linked node in constant time. And, also we need to maintain a head and tail dummy node, which allows us to add a new node to the end of the double linked list, and retrieve the head of the double linked list.
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 53 54 55 56 57 58 59 60 61 62 | class FirstUnique { public: struct ListNode { int val; ListNode* prev; ListNode* next; ListNode(int val) { this->val = val; prev = nullptr; next = nullptr; } }; FirstUnique(vector<int>& nums) { dummy = new ListNode(-1); tail = new ListNode(-1); for (const auto &n: nums) { add(n); } } int showFirstUnique() { if (dummy->next == nullptr) return -1; return dummy->next->val; } void add(int value) { // element is already added before if (data.find(value) != data.end()) { ListNode* cur = data[value]; if (cur == nullptr) return; if (cur->prev) { cur->prev->next = cur->next; } if (cur->next) { cur->next->prev = cur->prev; } if (cur == dummy->next) { dummy->next = cur->next; } if (tail->next == cur) { tail->next = cur->prev; } data[value] = nullptr; } else { // new unique number ListNode *cur = new ListNode(value); if (dummy->next == nullptr) { dummy->next = cur; } if (tail->next) { tail->next->next = cur; cur->prev = tail->next; } tail->next = cur; data[value] = cur; } } private: unordered_map<int, ListNode*> data; ListNode *dummy; ListNode *tail; }; |
class FirstUnique { public: struct ListNode { int val; ListNode* prev; ListNode* next; ListNode(int val) { this->val = val; prev = nullptr; next = nullptr; } }; FirstUnique(vector<int>& nums) { dummy = new ListNode(-1); tail = new ListNode(-1); for (const auto &n: nums) { add(n); } } int showFirstUnique() { if (dummy->next == nullptr) return -1; return dummy->next->val; } void add(int value) { // element is already added before if (data.find(value) != data.end()) { ListNode* cur = data[value]; if (cur == nullptr) return; if (cur->prev) { cur->prev->next = cur->next; } if (cur->next) { cur->next->prev = cur->prev; } if (cur == dummy->next) { dummy->next = cur->next; } if (tail->next == cur) { tail->next = cur->prev; } data[value] = nullptr; } else { // new unique number ListNode *cur = new ListNode(value); if (dummy->next == nullptr) { dummy->next = cur; } if (tail->next) { tail->next->next = cur; cur->prev = tail->next; } tail->next = cur; data[value] = cur; } } private: unordered_map<int, ListNode*> data; ListNode *dummy; ListNode *tail; };
Both operations are done in O(1) constant time, and O(N) space is required as we are using double linked list and a hash map to store the numbers in the queue.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:绝对的网赚干货 怎样通过做视频类网站赚钱 谈谈网站赚钱要点 如何让网站成为你赚钱的利器? 5种站长赚钱方法 你都了解吗? 分享如何通过互联网的网站赚钱 网站在建设时 文本该如何排版? 平面图形的知识和公式 小学数学线和角的知识 小学比和比例知识汇总 小学简易方程知识汇总
- 评论列表
-
- 添加评论