跳转至

LeetCode: 1206. 设计跳表

1、题目描述

不使用任何库函数,设计一个跳表。

跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计思想与链表相似。

例如,一个跳表包含 [30, 40, 50, 60, 70, 90],然后增加 80、45 到跳表中,以下图的方式操作:

img

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n)),空间复杂度是 O(n)

在本题中,你的设计应该要包含这些函数:

  • bool search(int target) : 返回target是否存在于跳表中。
  • void add(int num): 插入一个元素到跳表。
  • bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回false. 如果存在多个 num ,删除其中任意一个即可。 了解更多 : https://en.wikipedia.org/wiki/Skip_list

注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。

样例:

Skiplist skiplist = new Skiplist();

skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false,0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false,1 已被擦除

约束条件:

  • 0 <= num, target <= 20000
  • 最多调用 50000search, add, 以及 erase操作。

2、解题思路

- 设定一个最大的level值,每个节点同时保存当前的level

import random
import math


class Node:
    def __init__(self, value, levels):
        self.value = value
        self.levels = [None] * levels


class Skiplist:
    max_level = 16

    def __init__(self, init_value: int = -1, level: int = None):
        self.max_level = self.__class__.max_level if not level else level
        self.head = Node(init_value, self.max_level)

    def iter_levels(self, target):
        current = self.head
        for level in range(self.max_level - 1, -1, -1):
            while True:
                next_node = current.levels[level]
                if next_node and next_node.value < target:
                    current = next_node
                else:
                    break
            yield current, level

    def search(self, target: int) -> bool:
        prev = None
        for prev_node, _ in self.iter_levels(target):
            prev = prev_node
        current_node = prev.levels[0]
        return current_node and current_node.value == target

    def add(self, num: int) -> None:
        # current_level = random.randint(1, self.max_level)
        current_level = min(self.max_level, 1 + int(math.log2(1.0 / random.random())))
        node = Node(num, current_level)

        for prev, prev_level in self.iter_levels(num):
            if prev_level < current_level:
                next_node = prev.levels[prev_level]
                prev.levels[prev_level] = node
                node.levels[prev_level] = next_node

    def erase(self, num: int) -> bool:
        ans = False
        for prev, prev_level in self.iter_levels(num):
            next_node = prev.levels[prev_level]
            if next_node and next_node.value == num:
                ans = True
                prev.levels[prev_level] = next_node.levels[prev_level]
        return ans

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