{"id":7606,"date":"2020-11-06T13:19:24","date_gmt":"2020-11-06T21:19:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7606"},"modified":"2020-11-06T22:54:44","modified_gmt":"2020-11-07T06:54:44","slug":"leetcode-1206-design-skiplist","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/desgin\/leetcode-1206-design-skiplist\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1206. Design Skiplist"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1206. Design Skiplist - \u5237\u9898\u627e\u5de5\u4f5c EP367\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/783qX31AN08?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>\n<\/div><\/figure>\n\n\n\n<p>Design a Skiplist without using any built-in libraries.<\/p>\n\n\n\n<p><em>A Skiplist is a data structure that takes&nbsp;O(log(n)) time&nbsp;to&nbsp;<code>add<\/code>,&nbsp;<code>erase<\/code>&nbsp;and&nbsp;<code>search<\/code>. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be&nbsp;comparatively short and the idea behind Skiplists are just simple linked lists.<\/em><\/p>\n\n\n\n<p><em>For example:&nbsp;we have a Skiplist containing&nbsp;<code>[30,40,50,60,70,90]<\/code>&nbsp;and we want to add&nbsp;<code>80<\/code>&nbsp;and&nbsp;<code>45<\/code>&nbsp;into it. The&nbsp;Skiplist works this way:<\/em><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/09\/27\/1506_skiplist.gif\" alt=\"\"\/><\/figure>\n\n\n\n<p><br>Artyom Kalinin [CC BY-SA 3.0], via&nbsp;<a href=\"https:\/\/commons.wikimedia.org\/wiki\/File:Skip_list_add_element-en.gif\" target=\"_blank\" rel=\"noreferrer noopener\">Wikimedia Commons<\/a><\/p>\n\n\n\n<p><em>You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers,&nbsp;<code>add<\/code>&nbsp;,&nbsp;<code>erase<\/code>&nbsp;and&nbsp;<code>search&nbsp;<\/code>can be faster than O(n).&nbsp;It can be proven&nbsp;that the average time complexity for each operation is O(log(n)) and space complexity is O(n).<\/em><\/p>\n\n\n\n<p>To be specific, your design should include these functions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>bool search(int target)<\/code>&nbsp;: Return whether&nbsp;the&nbsp;<code>target<\/code>&nbsp;exists in the Skiplist&nbsp;or not.<\/li><li><code>void add(int num)<\/code>:&nbsp;Insert a value into the SkipList.&nbsp;<\/li><li><code>bool erase(int num)<\/code>: Remove a value in&nbsp;the Skiplist.&nbsp;If&nbsp;<code>num<\/code>&nbsp;does not exist in the Skiplist, do nothing and return false. If there exists multiple&nbsp;<code>num<\/code>&nbsp;values, removing&nbsp;any one of them is fine.<\/li><\/ul>\n\n\n\n<p>See more about Skiplist :&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Skip_list\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/en.wikipedia.org\/wiki\/Skip_list<\/a><\/p>\n\n\n\n<p>Note that duplicates may exist in the Skiplist, your code needs to handle this situation.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">Skiplist skiplist = new Skiplist();\n\nskiplist.add(1);\nskiplist.add(2);\nskiplist.add(3);\nskiplist.search(0);   \/\/ return false.\nskiplist.add(4);\nskiplist.search(1);   \/\/ return true.\nskiplist.erase(0);    \/\/ return false, 0 is not in skiplist.\nskiplist.erase(1);    \/\/ return true.\nskiplist.search(1);   \/\/ return false, 1 has already been erased.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0 &lt;= num, target&nbsp;&lt;= 20000<\/code><\/li><li>At most&nbsp;<code>50000<\/code>&nbsp;calls will be made to&nbsp;<code>search<\/code>,&nbsp;<code>add<\/code>, and&nbsp;<code>erase<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution:<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-1.png\" alt=\"\" class=\"wp-image-7610\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-2.png\" alt=\"\" class=\"wp-image-7611\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-3.png\" alt=\"\" class=\"wp-image-7612\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-4.png\" alt=\"\" class=\"wp-image-7613\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-5.png\" alt=\"\" class=\"wp-image-7614\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-5.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-5-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1206-ep367-5-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Skiplist {\npublic:\n  Skiplist() { head_ = make_shared<Node>(); }\n\n  bool search(int target) {\n    for (auto node = head_; node; node = node->down) {\n      while (node->next && node->next->val < target)\n        node = node->next;\n      if (node->next && node->next->val == target)\n        return true;\n    }\n    return false;\n  }\n\n  void add(int num) {\n    stack<shared_ptr<Node>> s;\n    shared_ptr<Node> down;\n    bool insert = true;\n    \n    for (auto node = head_; node; node = node->down) {\n      while (node->next && node->next->val < num)\n        node = node->next;\n      s.push(node);\n    }\n    \n    while (!s.empty() && insert) {\n      auto cur = s.top(); s.pop();\n      cur->next = make_shared<Node>(num, cur->next, down);\n      down = cur->next;\n      insert = rand() & 1; \/\/ 50% chance\n    }\n    \n    if (insert) \/\/ create a new layer.\n      head_ = make_shared<Node>(-1, nullptr, head_);\n  }\n\n  bool erase(int num) {\n    bool found = false;\n    for (auto node = head_; node; node = node->down) {\n      while (node->next && node->next->val < num)\n        node = node->next;\n      if (node->next && node->next->val == num) {\n        found = true;\n        node->next = node->next->next;\n      }\n    }\n    return found;\n  }\nprivate:\n  struct Node {\n    Node(int val = -1, \n         shared_ptr<Node> next = nullptr, \n         shared_ptr<Node> down = nullptr): \n          val(val), next(next), down(down) {}\n    int val;\n    shared_ptr<Node> next;\n    shared_ptr<Node> down;\n  };\n  \n  shared_ptr<Node> head_;\n};\n\n\/**\n * Your Skiplist object will be instantiated and called as such:\n * Skiplist* obj = new Skiplist();\n * bool param_1 = obj->search(target);\n * obj->add(num);\n * bool param_3 = obj->erase(num);\n *\/\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nimport random\n\nclass Node:\n  def __init__(self, val=-1, right=None, down=None):\n    self.val = val\n    self.right = right\n    self.down = down\n    \nclass Skiplist:\n  def __init__(self):\n    self.head = Node() # Dummy head\n\n  def search(self, target: int) -> bool:\n    node = self.head\n    while node:\n      # Move to the right in the current level\n      while node.right and node.right.val < target:\n        node = node.right\n      if node.right and node.right.val == target:\n        return True\n      # Move to the the next level\n      node = node.down\n    return False\n\n  def add(self, num: int) -> None:\n    nodes = []\n    node = self.head\n    while node:\n      # Move to the right in the current level\n      while node.right and node.right.val < num:\n        node = node.right\n      nodes.append(node)\n      # Move to the next level\n      node = node.down\n    \n    insert = True\n    down = None\n    while insert and nodes:\n      node = nodes.pop()\n      node.right = Node(num, node.right, down)\n      down = node.right\n      insert = (random.getrandbits(1) == 0)      \n    \n    # Create a new level with a dummy head.\n    # right = None\n    # down = current head\n    if insert:\n      self.head = Node(-1, None, self.head)\n\n  def erase(self, num: int) -> bool:\n    node = self.head\n    found = False\n    while node:\n      # Move to the right in the current level\n      while node.right and node.right.val < num:\n        node = node.right\n      # Find the target node\n      if node.right and node.right.val == num:\n        # Delete by skipping\n        node.right = node.right.right\n        found = True\n      # Move to the next level\n      node = node.down      \n    return found\n        \n# Your Skiplist object will be instantiated and called as such:\n# obj = Skiplist()\n# param_1 = obj.search(target)\n# obj.add(num)\n# param_3 = obj.erase(num)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Design a Skiplist without using any built-in libraries. A Skiplist is a data structure that takes&nbsp;O(log(n)) time&nbsp;to&nbsp;add,&nbsp;erase&nbsp;and&nbsp;search. Comparing with treap and red-black tree which has&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[340],"tags":[291,251,217,666],"class_list":["post-7606","post","type-post","status-publish","format-standard","hentry","category-desgin","tag-data-structure","tag-design","tag-hard","tag-skiplist","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7606","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=7606"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7606\/revisions"}],"predecessor-version":[{"id":7615,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7606\/revisions\/7615"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7606"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7606"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7606"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}