{"id":2434,"date":"2018-04-06T21:44:37","date_gmt":"2018-04-07T04:44:37","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2434"},"modified":"2018-04-06T22:37:16","modified_gmt":"2018-04-07T05:37:16","slug":"leetcode-432-all-oone-data-structure","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-432-all-oone-data-structure\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 432. All O`one Data Structure"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 432. All O`one Data Structure - \u5237\u9898\u627e\u5de5\u4f5c EP178\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/wYqLisoH80w?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>Problem<\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u8bbe\u8ba1\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff0c\u652f\u6301inc\/dec\/getmaxkey\/getminkey\u64cd\u4f5c\uff0c\u5fc5\u987b\u90fd\u5728O(1)\u65f6\u95f4\u5185\u5b8c\u6210\u3002<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/all-oone-data-structure\/description\/\">https:\/\/leetcode.com\/problems\/all-oone-data-structure\/description\/<\/a><\/p>\n<div class=\"question-description\">\n<div>\n<p>Implement a data structure supporting the following operations:<\/p>\n<ol>\n<li>Inc(Key) &#8211; Inserts a new key\u00a0with value 1. Or increments an existing key by 1. Key is guaranteed to be a\u00a0<b>non-empty<\/b>\u00a0string.<\/li>\n<li>Dec(Key) &#8211; If Key&#8217;s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a\u00a0<b>non-empty<\/b>\u00a0string.<\/li>\n<li>GetMaxKey() &#8211; Returns one of the keys with maximal value. If no element exists, return an empty string\u00a0<code>\"\"<\/code>.<\/li>\n<li>GetMinKey() &#8211; Returns one of the keys with minimal value. If no element exists, return an empty string\u00a0<code>\"\"<\/code>.<\/li>\n<\/ol>\n<p>Challenge: Perform all these in O(1) time complexity.<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2439\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/432-ep178.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/432-ep178.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/432-ep178-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/04\/432-ep178-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<\/div>\n<h1><strong>Solution<\/strong><\/h1>\n<p>Time complexity: O(1)<\/p>\n<p>Space complexity: O(n), n = # of unique keys<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 32 ms\r\nclass AllOne {\r\npublic:\r\n  \/** Initialize your data structure here. *\/\r\n  AllOne() {}\r\n\r\n  \/** Inserts a new key &lt;Key&gt; with value 1. Or increments an existing key by 1. *\/\r\n  void inc(string key) {\r\n    auto it = m_.find(key);\r\n    \r\n    if (it == m_.end()) {\r\n      if (l_.empty() || l_.front().value != 1) \r\n        l_.push_front({1, {key}});\r\n      else\r\n        l_.front().keys.insert(key);\r\n      m_[key] = l_.begin();\r\n      return;\r\n    }\r\n    \r\n    auto lit = it-&gt;second;\r\n    \r\n    auto nit = next(lit);\r\n    if (nit == l_.end() || nit-&gt;value != lit-&gt;value + 1)\r\n      nit = l_.insert(nit, {lit-&gt;value + 1, {}});\r\n    nit-&gt;keys.insert(key);\r\n    m_[key] = nit;\r\n    \r\n    remove(lit, key);\r\n  }\r\n\r\n  \/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. *\/\r\n  void dec(string key) {\r\n    auto it = m_.find(key);\r\n    if (it == m_.end()) return;\r\n    \r\n    auto lit = it-&gt;second;\r\n        \r\n    if (lit-&gt;value &gt; 1) {\r\n      auto pit = prev(lit);\r\n      if (lit == l_.begin() || pit-&gt;value != lit-&gt;value - 1)\r\n        pit = l_.insert(lit, {lit-&gt;value - 1, {}});\r\n      pit-&gt;keys.insert(key);\r\n      m_[key] = pit;\r\n    } else {\r\n      \/\/ value == 1, remove from the data structure\r\n      m_.erase(key);\r\n    }\r\n    \r\n    remove(lit, key);    \r\n  }\r\n\r\n  \/** Returns one of the keys with maximal value. *\/\r\n  string getMaxKey() {\r\n    return l_.empty() ? \"\" : *l_.back().keys.cbegin();\r\n  }\r\n\r\n  \/** Returns one of the keys with Minimal value. *\/\r\n  string getMinKey() {\r\n    return l_.empty() ? \"\" : *l_.front().keys.cbegin();\r\n  }\r\nprivate:\r\n  struct Node {  \r\n    int value;\r\n    unordered_set&lt;string&gt; keys;\r\n  };\r\n  \r\n  list&lt;Node&gt; l_;\r\n  unordered_map&lt;string, list&lt;Node&gt;::iterator&gt; m_;\r\n  \r\n  \/\/ Remove from old node.\r\n  void remove(list&lt;Node&gt;::iterator it, const string&amp; key) {\r\n    it-&gt;keys.erase(key);\r\n    if (it-&gt;keys.empty())\r\n      l_.erase(it);\r\n  }\r\n};<\/pre>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-460-lfu-cache\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 460. LFU Cache \u82b1\u82b1\u9171<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-146-lru-cache\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 146. LRU Cache O(1)<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-380-insert-delete-getrandom-o1\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 380. Insert Delete GetRandom O(1)<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-381-insert-delete-getrandom-o1-duplicates-allowed\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 381. Insert Delete GetRandom O(1) &amp;#8211; Duplicates allowed<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u8bbe\u8ba1\u4e00\u79cd\u6570\u636e\u7ed3\u6784\uff0c\u652f\u6301inc\/dec\/getmaxkey\/getminkey\u64cd\u4f5c\uff0c\u5fc5\u987b\u90fd\u5728O(1)\u65f6\u95f4\u5185\u5b8c\u6210\u3002 https:\/\/leetcode.com\/problems\/all-oone-data-structure\/description\/ Implement a data structure supporting the following operations: Inc(Key) &#8211; Inserts a new key\u00a0with value 1. Or increments an existing key by&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89,70,50],"tags":[291,251,217,92],"class_list":["post-2434","post","type-post","status-publish","format-standard","hentry","category-data-structure","category-hashtable","category-list","tag-data-structure","tag-design","tag-hard","tag-o1","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2434","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2434"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2434\/revisions"}],"predecessor-version":[{"id":2440,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2434\/revisions\/2440"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2434"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2434"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2434"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}