Problem

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 is 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:

skiplist

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).

See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list

Implement the Skiplist class:

  • Skiplist() Initializes the object of the skiplist.
  • bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise.
  • void add(int num) Inserts the value num into the SkipList.
  • bool erase(int num) Removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine.

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

https://leetcode.com/problems/design-skiplist/

Example 1:

Input
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
Output
[null, null, null, null, false, null, true, false, true, false]

Explanation

1
2
3
4
5
6
7
8
9
10
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 <= 2 * 10⁴
  • At most 5 * 10⁴ calls will be made to search, add, and erase.

Test Cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Skiplist:

    def __init__(self):


    def search(self, target: int) -> bool:


    def add(self, num: int) -> None:


    def erase(self, num: int) -> bool:



# 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)
solution_test.py
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
import pytest

from solution import Skiplist

null = None
false = False
true = True


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"],
        [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]],
        [null, null, null, null, false, null, true, false, true, false]
    ),

    (
        ['Skiplist', 'add', 'add', 'add', 'add', 'add', 'add', 'search', 'add', 'add', 'search'],
        [[], [30], [40], [50], [60], [70], [90], [45], [80], [45]],
        [None, None, None, None, None, None, None, False, None, None, True]
    ),
])
@pytest.mark.parametrize('clazz', [Skiplist])
def test_solution(clazz, actions, params, expects):
    sol = None
    for action, args, expected in zip(actions, params, expects):
        if action == 'Skiplist':
            sol = clazz(*args)
        else:
            assert getattr(sol, action)(*args) == expected

Thoughts

就像处理普通的链表那样，加一个虚拟的 head 节点可以简化边界处理。

另外跳表在插入的时候，已经在某一层插入了，是否需要在上一层也加入，可以引入随机判断。

PS: 加了个 format 方法把当前跳板格式化成字符串。如

1
2
3
4
HEAD----->40----------------->80----->NIL
HEAD----->40------------->70->80----->NIL
HEAD->30->40--------->60->70->80->90->NIL
HEAD->30->40->45->50->60->70->80->90->NIL

Code

solution.py
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
from random import randrange


class Node:
    def __init__(self, val=None):
        self.val = val
        self.rights: list['Node'|None] = []


class Skiplist:

    def __init__(self):
        self._head = Node() # A virtual head node to simplify boundary case processing.
        self._head.rights.append(None)

    def search(self, target: int) -> bool:
        node = self._head
        while node:
            for r in reversed(node.rights):
                if not r: continue
                if r.val == target:
                    return True
                if r.val < target:
                    node = r
                    break
            else:
                return False

        return False


    def add(self, num: int) -> None:
        node = self._head
        parents: list[Node] = []
        while node:
            for r in reversed(node.rights):
                if r and r.val <= num: # Stable sort.
                    node = r
                    break
                else:
                    parents.append(node)
            else:
                break

        new_node = Node(num)
        level = 0
        need_ins = 1
        while need_ins:
            if level < len(parents):
                parent = parents[-1 - level]
            else:
                parent = self._head
                parent.rights.append(None)

            new_node.rights.append(parent.rights[level])
            parent.rights[level] = new_node
            level += 1
            need_ins = randrange(2) # Randomly choose whether to promote it to next level.

    def erase(self, num: int) -> bool:
        node = self._head
        parents = []
        while node:
            for r in reversed(node.rights):
                if r and r.val < num: # Remove the left-most when multiple same numbers.
                    node = r
                    break
                else:
                    parents.append(node)
            else: break

        node = parents[-1].rights[0]
        if not node or node.val != num:
            return False

        for level in range(len(node.rights)):
            parents[-1 - level].rights[level] = node.rights[level]

        return True

    def format(self) -> str:
        height = len(self._head.rights)
        layers = [['HEAD'] for _ in range(height)]

        node = self._head.rights[0]
        while node:
            level = len(node.rights)

            part = f'>{node.val}'
            for i in range(level):
                layers[i].append(part)

            part = '-' * len(part)
            for i in range(level, height):
                layers[i].append(part)

            node = node.rights[0]

        for layer in layers:
            layer.append('>NIL')

        layers.reverse()
        layers.append('')
        return '\n'.join('-'.join(layer) for layer in layers)


# 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)
hard
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~