1206. 设计跳表

Hard

题目描述

设计一个不使用任何内置库的跳表。

跳表是一种数据结构，它使用 O(log(n)) 的时间来添加、删除和搜索。与具有相同功能和性能的 treap 和红黑树相比，跳表的代码长度可以相对较短，跳表背后的思想就是简单的链表。

例如，我们有一个包含 [30,40,50,60,70,90] 的跳表，我们想要添加 80 和 45。跳表的工作方式如下：

你可以看到跳表中有许多层。每一层都是一个排序的链表。在上层的帮助下，添加、删除和搜索可以比 O(n) 更快。可以证明每个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

实现 Skiplist 类：

Skiplist() 初始化跳表对象。
bool search(int target) 如果整数 target 存在于跳表中，返回 true；否则返回 false。
void add(int num) 将值 num 插入跳表中。
bool erase(int num) 从跳表中删除值 num 并返回 true。如果 num 不存在于跳表中，不做任何操作并返回 false。如果存在多个 num 值，删除其中任何一个都可以。

注意跳表中可能存在重复值，你的代码需要处理这种情况。

示例 1：

输入
["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 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 <= 2 * 10^4
最多调用 5 * 10^4 次 search、add 和 erase。

解题思路

跳表是一种概率数据结构，其核心思想是通过多层链表来实现快速查找。

基本原理：

多层结构：跳表由多层有序链表组成，底层包含所有元素，上层是下层的子集
随机化层数：新插入的节点通过抛硬币决定层数，每次有 1/2 的概率向上一层
快速定位：查找时从最高层开始，向右移动直到下一个节点值大于目标值，然后向下一层继续查找

实现要点：

节点结构：每个节点包含值和指向各层下一个节点的指针数组
哨兵节点：使用头节点简化边界处理
查找路径记录：在插入和删除时需要记录每层的前驱节点

算法步骤：

搜索：从最高层开始，逐层向下查找目标值
插入：先查找插入位置，随机决定新节点层数，然后在各层插入
删除：查找目标节点，记录路径，然后在各层删除对应节点

这种设计使得平均时间复杂度达到 O(log n)，同时实现相对简单。

代码实现

class Skiplist {
private:
    struct Node {
        int val;
        vector<Node*> next;
        Node(int v, int level) : val(v), next(level + 1, nullptr) {}
    };
    
    Node* head;
    int maxLevel;
    
    int randomLevel() {
        int level = 0;
        while (rand() % 2 && level < 15) level++;
        return level;
    }
    
    vector<Node*> findPath(int target) {
        vector<Node*> path(maxLevel + 1);
        Node* curr = head;
        
        for (int i = maxLevel; i >= 0; i--) {
            while (curr->next[i] && curr->next[i]->val < target) {
                curr = curr->next[i];
            }
            path[i] = curr;
        }
        return path;
    }
    
public:
    Skiplist() {
        maxLevel = 0;
        head = new Node(-1, 16);
    }
    
    bool search(int target) {
        auto path = findPath(target);
        Node* node = path[0]->next[0];
        return node && node->val == target;
    }
    
    void add(int num) {
        auto path = findPath(num);
        int level = randomLevel();
        
        if (level > maxLevel) {
            for (int i = maxLevel + 1; i <= level; i++) {
                path.push_back(head);
            }
            maxLevel = level;
        }
        
        Node* newNode = new Node(num, level);
        for (int i = 0; i <= level; i++) {
            newNode->next[i] = path[i]->next[i];
            path[i]->next[i] = newNode;
        }
    }
    
    bool erase(int num) {
        auto path = findPath(num);
        Node* node = path[0]->next[0];
        
        if (!node || node->val != num) return false;
        
        for (int i = 0; i < node->next.size(); i++) {
            path[i]->next[i] = node->next[i];
        }
        
        delete node;
        
        while (maxLevel > 0 && !head->next[maxLevel]) {
            maxLevel--;
        }
        
        return true;
    }
};

import random

class Skiplist:
    class Node:
        def __init__(self, val, level):
            self.val = val
            self.next = [None] * (level + 1)
    
    def __init__(self):
        self.max_level = 0
        self.head = self.Node(-1, 16)
    
    def _random_level(self):
        level = 0
        while random.randint(0, 1) and level < 15:
            level += 1
        return level
    
    def _find_path(self, target):
        path = [None] * (self.max_level + 1)
        curr = self.head
        
        for i in range(self.max_level, -1, -1):
            while curr.next[i] and curr.next[i].val < target:
                curr = curr.next[i]
            path[i] = curr
        
        return path
    
    def search(self, target: int) -> bool:
        path = self._find_path(target)
        node = path[0].next[0]
        return node is not None and node.val == target
    
    def add(self, num: int) -> None:
        path = self._find_path(num)
        level = self._random_level()
        
        if level > self.max_level:
            for i in range(self.max_level + 1, level + 1):
                path.append(self.head)
            self.max_level = level
        
        new_node = self.Node(num, level)
        for i in range(level + 1):
            new_node.next[i] = path[i].next[i]
            path[i].next[i] = new_node
    
    def erase(self, num: int) -> bool:
        path = self._find_path(num)
        node = path[0].next[0]
        
        if not node or node.val != num:
            return False
        
        for i in range(len(node.next)):
            path[i].next[i] = node.next[i]
        
        while self.max_level > 0 and not self.head.next[self.max_level]:
            self.max_level -= 1
        
        return True

public class Skiplist {
    private class Node {
        public int val;
        public Node[] next;
        
        public Node(int v, int level) {
            val = v;
            next = new Node[level + 1];
        }
    }
    
    private Node head;
    private int maxLevel;
    private Random rand;
    
    public Skiplist() {
        maxLevel = 0;
        head = new Node(-1, 16);
        rand = new Random();
    }
    
    private int RandomLevel() {
        int level = 0;
        while (rand.Next(2) == 1 && level < 15) level++;
        return level;
    }
    
    private Node[] FindPath(int target) {
        Node[] path = new Node[maxLevel + 1];
        Node curr = head;
        
        for (int i = maxLevel; i >= 0; i--) {
            while (curr.next[i] != null && curr.next[i].val < target) {
                curr = curr.next[i];
            }
            path[i] = curr;
        }
        return path;
    }
    
    public bool Search(int target) {
        Node[] path = FindPath(target);
        Node node = path[0].next[0];
        return node != null && node.val == target;
    }
    
    public void Add(int num) {
        Node[] path = FindPath(num);
        int level = RandomLevel();
        
        if (level > maxLevel) {
            Array.Resize(ref path, level + 1);
            for (int i = maxLevel + 1; i <= level; i++) {
                path[i] = head;
            }
            maxLevel = level;
        }
        
        Node newNode = new Node(num, level);
        for (int i = 0; i <= level; i++) {
            newNode.next[i] = path[i].next[i];
            path[i].next[i] = newNode;
        }
    }
    
    public bool Erase(int num) {
        Node[] path = FindPath(num);
        Node node = path[0].next[0];
        
        if (node == null || node.val != num) return false;
        
        for (int i = 0; i < node.next.Length; i++) {
            path[i].next[i] = node.next[i];
        }
        
        while (maxLevel > 0 && head.next[maxLevel] == null) {
            maxLevel--;
        }
        
        return true;
    }
}

class Node {
    constructor(val, level) {
        this.val = val;
        this.forward = new Array(level + 1).fill(null);
    }
}

var Skiplist = function() {
    this.maxLevel = 16;
    this.level = 0;
    this.header = new Node(-1, this.maxLevel);
};

Skiplist.prototype.randomLevel = function() {
    let level = 0;
    while (Math.random() < 0.5 && level < this.maxLevel) {
        level++;
    }
    return level;
};

Skiplist.prototype.search = function(target) {
    let current = this.header;
    
    for (let i = this.level; i >= 0; i--) {
        while (current.forward[i] && current.forward[i].val < target) {
            current = current.forward[i];
        }
    }
    
    current = current.forward[0];
    return current && current.val === target;
};

Skiplist.prototype.add = function(num) {
    let update = new Array(this.maxLevel + 1).fill(null);
    let current = this.header;
    
    for (let i = this.level; i >= 0; i--) {
        while (current.forward[i] && current.forward[i].val < num) {
            current = current.forward[i];
        }
        update[i] = current;
    }
    
    let newLevel = this.randomLevel();
    
    if (newLevel > this.level) {
        for (let i = this.level + 1; i <= newLevel; i++) {
            update[i] = this.header;
        }
        this.level = newLevel;
    }
    
    let newNode = new Node(num, newLevel);
    for (let i = 0; i <= newLevel; i++) {
        newNode.forward[i] = update[i].forward[i];
        update[i].forward[i] = newNode;
    }
};

Skiplist.prototype.erase = function(num) {
    let update = new Array(this.maxLevel + 1).fill(null);
    let current = this.header;
    
    for (let i = this.level; i >= 0; i--) {
        while (current.forward[i] && current.forward[i].val < num) {
            current = current.forward[i];
        }
        update[i] = current;
    }
    
    current = current.forward[0];
    
    if (!current || current.val !== num) {
        return false;
    }
    
    for (let i = 0; i <= this.level; i++) {
        if (update[i].forward[i] !== current) {
            break;
        }
        update[i].forward[i] = current.forward[i];
    }
    
    while (this.level > 0 && !this.header.forward[this.level]) {
        this.level--;
    }
    
    return true;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
搜索	O(log n)	O(1)
插入	O(log n)	O(1)
删除	O(log n)	O(1)
整体空间	-	O(n)

其中 n 为跳表中元素的个数。跳表的平均时间复杂度为 O(log n)，最坏情况下为 O(n)（当所有节点都只在底层时），但概率极小。空间复杂度为 O(n)，额外空间主要用于存储多层指针。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目