Design a Skiplist without using any built-in libraries.
A Skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists are just simple linked lists.
For example: we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add , erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).
To be specific, your design should include these functions:
bool search(int target): Return whether thetargetexists in the Skiplist or not.void add(int num): Insert a value into the SkipList.bool erase(int num): Remove a value in the Skiplist. Ifnumdoes not exist in the Skiplist, do nothing and return false. If there exists multiplenumvalues, removing any one of them is fine.
See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list
Note that duplicates may exist in the Skiplist, your code needs to handle this situation.
Example:
|
1 2 3 4 5 6 7 8 9 10 11 |
Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // return false. skiplist.add(4); skiplist.search(1); // return true. skiplist.erase(0); // return false, 0 is not in skiplist. skiplist.erase(1); // return true. skiplist.search(1); // return false, 1 has already been erased. |
Constraints:
0 <= num, target <= 20000- At most
50000calls will be made tosearch,add, anderase.
Solution:
C++
|
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 63 64 65 66 67 68 69 70 |
// Author: Huahua class Skiplist { public: Skiplist() { head_ = make_shared<Node>(); } bool search(int target) { for (auto node = head_; node; node = node->down) { while (node->next && node->next->val < target) node = node->next; if (node->next && node->next->val == target) return true; } return false; } void add(int num) { stack<shared_ptr<Node>> s; shared_ptr<Node> down; bool insert = true; for (auto node = head_; node; node = node->down) { while (node->next && node->next->val < num) node = node->next; s.push(node); } while (!s.empty() && insert) { auto cur = s.top(); s.pop(); cur->next = make_shared<Node>(num, cur->next, down); down = cur->next; insert = rand() & 1; // 50% chance } if (insert) // create a new layer. head_ = make_shared<Node>(-1, nullptr, head_); } bool erase(int num) { bool found = false; for (auto node = head_; node; node = node->down) { while (node->next && node->next->val < num) node = node->next; if (node->next && node->next->val == num) { found = true; node->next = node->next->next; } } return found; } private: struct Node { Node(int val = -1, shared_ptr<Node> next = nullptr, shared_ptr<Node> down = nullptr): val(val), next(next), down(down) {} int val; shared_ptr<Node> next; shared_ptr<Node> down; }; shared_ptr<Node> head_; }; /** * Your Skiplist object will be instantiated and called as such: * Skiplist* obj = new Skiplist(); * bool param_1 = obj->search(target); * obj->add(num); * bool param_3 = obj->erase(num); */ |
Python3
|
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 63 64 65 66 67 68 69 70 |
import random class Node: def __init__(self, val=-1, right=None, down=None): self.val = val self.right = right self.down = down class Skiplist: def __init__(self): self.head = Node() # Dummy head def search(self, target: int) -> bool: node = self.head while node: # Move to the right in the current level while node.right and node.right.val < target: node = node.right if node.right and node.right.val == target: return True # Move to the the next level node = node.down return False def add(self, num: int) -> None: nodes = [] node = self.head while node: # Move to the right in the current level while node.right and node.right.val < num: node = node.right nodes.append(node) # Move to the next level node = node.down insert = True down = None while insert and nodes: node = nodes.pop() node.right = Node(num, node.right, down) down = node.right insert = (random.getrandbits(1) == 0) # Create a new level with a dummy head. # right = None # down = current head if insert: self.head = Node(-1, None, self.head) def erase(self, num: int) -> bool: node = self.head found = False while node: # Move to the right in the current level while node.right and node.right.val < num: node = node.right # Find the target node if node.right and node.right.val == num: # Delete by skipping node.right = node.right.right found = True # Move to the next level node = node.down return found # Your Skiplist object will be instantiated and called as such: # obj = Skiplist() # param_1 = obj.search(target) # obj.add(num) # param_3 = obj.erase(num) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment