azl397985856 commented 1 year ago

1206. 设计跳表

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

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

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

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

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
最多调用 50000 次 search, add, 以及 erase操作。

Diana21170648 commented 1 year ago

思路

从上往下查询从下往上删除

代码

class Node:
    def __init__(self,val=0,right=None,down=None):
        self.val=val
        self.right=right
        self.down=down

class Skiplist:
    def __init__(self):
        left=[Node(-1) for _ in range(16)]
        right=[Node(20001) for _ in range(16)]
        for i in range(15):
            left[i].right=right[i]
            left[i].down=left[i+1]
            right[i].down=right[i+1]
        left[-1].right=right[-1]
        self.root=left[0]

    def search(self, target: int) -> bool:
        cur=self.root
        while cur:
            if target<cur.right.val:
                cur=cur.down
            elif target>cur.right.val:
                cur=cur.right
            else:
                return True
        return False

    def add(self, num: int) -> None:
        cur=self.root
        stack=[]
        while cur:
            if cur.right.val>=num:
                stack.append(cur)
                cur=cur.down
            else:
                cur=cur.right
        pre=None
        while stack:
            cur=stack.pop()
            node=Node(num)
            node.right=cur.right
            cur.right=node
            if pre:
                node.down=pre
            pre=node
            if random.randint(0,1):
                break

    def erase(self, num: int) -> bool:
        cur=self.root
        removed=False
        while cur:
            if num<cur.right.val:
                cur=cur.down
            elif num>cur.right.val:
                cur=cur.right
            else:
                cur.right=cur.right.right
                removed=True
                cur=cur.down
        return removed

复杂度分析

时间复杂度：O(logN)，增删查复杂度。
空间复杂度：O(N)

Alexno1no2 commented 1 year ago

# 1 先创建一个跳表节点Node，需要包含以下三个参数
    # 节点值val
    # 右边节点right
    # 下边节点down
# 2 跳表初始化
    # 每一层设置左右两个哨兵节点，左节点的值要比所有值小，右节点的值要比所有值大。因为0 <= num, target <= 20000，因此左节点值设为 -1，右节点值设为20001即可。
    # 跳表的最大层数为16。因为题目说了最多调用 50000 次 search, add, 以及 erase操作，也就是底层链表长度n最长为50000，而我们随机的选 n/2  个元素做为一级索引，随机选 n/4 个元素作为二级索引，……，随机选n/2^k 作为顶层索引。而 2^16=65536>50000 所以16层足够为长度50000的链表建立索引。
    # 每层的两个哨兵节点中，左节点要指向右节点，并且除了最后一层外左右节点都需要指向下一层节点
    # 跳表起始节点head即为left[0]，即顶层的左哨兵节点
# 3 查找(search)方法。
    #从head节点开始查找，如果当前节点cur的右边节点值比target大，应该往下查找；如果cur的右边节点值比target小，应该往右查找；如果相等，那就是找到了，返回True。遍历完了也没找到，返回False。
# 4 插入(add)方法。
    # 相对比较复杂，因为还需要根据概率维护索引。
    # 查找插入位置。也是从head开始查找插入的位置，每次往下走的节点都需要保存，因为可能在该节点后面插入新的节点作为索引。换句话说，其实查找的是在每一层应该插入的位置并记录在stack中，只是不一定每一层都会插入节点罢了。
    # 插入节点。首先最后一层肯定是要插入节点的，插入完成后，记录一下该层节点，因为如果该节点要加入到索引中，上一层是要指向这一层的。以1/2的概率生成索引，在上一层插入节点；1/2的概率插入结束，不再继续维护索引；如果前面生成了索引，再以1/2的概率插入节点直到插入到顶层或中途因概率停止插入。
# 5 删除(erase)方法。
    # 删除和查找差不多，只不过是对每一层找到的节点都要进行删除，也就是删除节点的同时要删除由其产生的索引节点。

class Node:
    def __init__(self, val = 0):
        self.val = val
        self.right = None
        self.down = None

class Skiplist:

    def __init__(self):
        # 每层设置两个哨兵节点，左节点的值要比所有值小，右节点的值要比所有值大。16是跳表的最大层数
        left = [Node(-1) for _ in range(16)]
        right = [Node(20001) for _ in range(16)]
        for i in range(15):
            left[i].right = right[i]
            left[i].down = left[i + 1]
            right[i].down = right[i + 1]
        left[-1].right = right[-1]
        self.head = left[0]

    def search(self, target: int) -> bool:
        cur = self.head
        while cur:
            if cur.right.val > target:
                cur = cur.down
            elif cur.right.val < target:
                cur = cur.right
            else:
                return True
        return False

    def add(self, num: int) -> None:
        cur = self.head
        stack = []

        while cur:
            if cur.right.val >= num:
                stack.append(cur)
                cur = cur.down
            else:
                cur = cur.right
        pre = None

        while stack:
            cur = stack.pop()
            node = Node(num)
            node.right = cur.right
            cur.right = node
            if pre: 
                node.down = pre
            pre = node
            if random.randint(0, 1): 
                break

    def erase(self, num: int) -> bool:
        cur = self.head
        is_removed = False
        while cur:
            if cur.right.val >= num:
                if cur.right.val == num:
                    is_removed = True
                    cur.right = cur.right.right
                cur = cur.down
            else:
                cur = cur.right
        return is_removed

GuitarYs commented 1 year ago

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.down = None

class Skiplist:
    def __init__(self):
        self.head = Node(-1)
        self.levels = [self.head]

    def search(self, target):
        curr = self.head
        while curr is not None:
            if curr.val == target:
                return True
            elif curr.next is None or curr.next.val > target:
                curr = curr.down
            else:
                curr = curr.next
        return False

    def add(self, num):
        path = self._get_path()
        node = Node(num)
        prev = None
        while path:
            curr = path.pop()
            node.next = curr.next
            curr.next = node
            node.down = prev
            prev = node
            if random.random() < 0.5:
                new_level = Node(-1)
                new_level.next = self.levels[-1]
                self.levels.append(new_level)
                new_level.down = prev
                prev = new_level

    def erase(self, num):
        found = False
        curr = self.head
        while curr is not None:
            if curr.val == num:
                curr.next = curr.next.next
                found = True
            elif curr.next is None or curr.next.val > num:
                curr = curr.down
            else:
                curr = curr.next
        return found

    def _get_path(self):
        path = []
        curr = self.head
        while curr is not None:
            if curr.next is None:
                path.append(curr)
                curr = curr.down
            elif curr.next.val == float('inf'):
                break
            elif curr.next.val > float('inf'):
                curr = curr.down
            else:
                curr = curr.next
        return path

Fuku-L commented 1 year ago

代码

class Skiplist {
    static final int MAX_LEVEL = 32;
    static final double P_FACTOR = 0.25;
    private SkiplistNode head;
    private int level;
    private Random random;

    public Skiplist() {
        this.head = new SkiplistNode(-1, MAX_LEVEL);
        this.level = 0;
        this.random = new Random();
    }

    public boolean search(int target) {
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 target 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        /* 检测当前元素的值是否等于 target */
        if (curr != null && curr.val == target) {
            return true;
        } 
        return false;
    }

    public void add(int num) {
        SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
        Arrays.fill(update, head);
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        int lv = randomLevel();
        level = Math.max(level, lv);
        SkiplistNode newNode = new SkiplistNode(num, lv);
        for (int i = 0; i < lv; i++) {
            /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
        SkiplistNode curr = this.head;
        for (int i = level - 1; i >= 0; i--) {
            /* 找到第 i 层小于且最接近 num 的元素*/
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        /* 如果值不存在则返回 false */
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i].forward[i] != curr) {
                break;
            }
            /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
            update[i].forward[i] = curr.forward[i];
        }
        /* 更新当前的 level */
        while (level > 1 && head.forward[level - 1] == null) {
            level--;
        }
        return true;
    }

    private int randomLevel() {
        int lv = 1;
        /* 随机生成 lv */
        while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
            lv++;
        }
        return lv;
    }
}

class SkiplistNode {
    int val;
    SkiplistNode[] forward;

    public SkiplistNode(int val, int maxLevel) {
        this.val = val;
        this.forward = new SkiplistNode[maxLevel];
    }
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist obj = new Skiplist();
 * boolean param_1 = obj.search(target);
 * obj.add(num);
 * boolean param_3 = obj.erase(num);
 */

leetcode-pp / 91alg-11-daily-check

【Day 91 】2023-09-08 - 1206. 设计跳表 #93

1206. 设计跳表

入选理由

题目地址

前置知识

题目描述

思路

代码

代码