LeetCode 1206. 设计跳表

Categories:

题目描述
思路分析
1. 解法一：跳表（推荐）
相似题目

题目描述

✅ 1206. 设计跳表

思路分析

解法一：跳表（推荐）

核心思路：

用多层有序链表加速查找，底层包含所有元素，上层按概率提升。

查找/插入/删除都从最高层向下逐层定位。

维护 MAX_LEVEL 与随机升层函数。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示跳表中元素数量。

空间复杂度：O(n)，存储所有节点与多层索引。

class Skiplist {
    private static class Node {
        int val;
        Node[] next;

        Node(int val, int level) {
            this.val = val;
            this.next = new Node[level];
        }
    }

    private static final int MAX_LEVEL = 32;
    private static final double P = 0.25;

    private final Node head = new Node(-1, MAX_LEVEL);
    private int level = 1;
    private final Random random = new Random();

    public boolean search(int target) {
        Node cur = head;

        // 从最高层向下定位
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target) {
                cur = cur.next[i];
            }
        }

        cur = cur.next[0];
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Node cur = head;

        // 记录每层的前驱节点
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            update[i] = cur;
        }

        int lvl = randomLevel();
        if (lvl > level) {
            for (int i = level; i < lvl; i++) {
                update[i] = head;
            }
            level = lvl;
        }

        Node node = new Node(num, lvl);
        for (int i = 0; i < lvl; i++) {
            node.next[i] = update[i].next[i];
            update[i].next[i] = node;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Node cur = head;

        // 记录每层的前驱节点
        for (int i = level - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            update[i] = cur;
        }

        cur = cur.next[0];
        if (cur == null || cur.val != num) {
            return false;
        }

        for (int i = 0; i < level; i++) {
            if (update[i].next[i] != cur) {
                break;
            }
            update[i].next[i] = cur.next[i];
        }

        while (level > 1 && head.next[level - 1] == null) {
            level--;
        }

        return true;
    }

    private int randomLevel() {
        int lvl = 1;
        while (lvl < MAX_LEVEL && random.nextDouble() < P) {
            lvl++;
        }
        return lvl;
    }
}

type Skiplist struct {
	level int
	head  *Node
}

type Node struct {
	val  int
	next []*Node
}

const maxLevel = 32
const pFactor = 0.25

func Constructor() Skiplist {
	head := &Node{val: -1, next: make([]*Node, maxLevel)}
	return Skiplist{level: 1, head: head}
}

func (s *Skiplist) Search(target int) bool {
	cur := s.head

	// 从最高层向下定位
	for i := s.level - 1; i >= 0; i-- {
		for cur.next[i] != nil && cur.next[i].val < target {
			cur = cur.next[i]
		}
	}

	cur = cur.next[0]
	return cur != nil && cur.val == target
}

func (s *Skiplist) Add(num int) {
	update := make([]*Node, maxLevel)
	cur := s.head

	// 记录每层的前驱节点
	for i := s.level - 1; i >= 0; i-- {
		for cur.next[i] != nil && cur.next[i].val < num {
			cur = cur.next[i]
		}
		update[i] = cur
	}

	lvl := randomLevel()
	if lvl > s.level {
		for i := s.level; i < lvl; i++ {
			update[i] = s.head
		}
		s.level = lvl
	}

	node := &Node{val: num, next: make([]*Node, lvl)}
	for i := 0; i < lvl; i++ {
		node.next[i] = update[i].next[i]
		update[i].next[i] = node
	}
}

func (s *Skiplist) Erase(num int) bool {
	update := make([]*Node, maxLevel)
	cur := s.head

	// 记录每层的前驱节点
	for i := s.level - 1; i >= 0; i-- {
		for cur.next[i] != nil && cur.next[i].val < num {
			cur = cur.next[i]
		}
		update[i] = cur
	}

	cur = cur.next[0]
	if cur == nil || cur.val != num {
		return false
	}

	for i := 0; i < s.level; i++ {
		if update[i].next[i] != cur {
			break
		}
		update[i].next[i] = cur.next[i]
	}

	for s.level > 1 && s.head.next[s.level-1] == nil {
		s.level--
	}

	return true
}

func randomLevel() int {
	lvl := 1
	for lvl < maxLevel && rand.Float64() < pFactor {
		lvl++
	}
	return lvl
}

相似题目

题目	难度	考察点
380. O(1) 时间插入、删除和获取随机元素	中等	设计数据结构
381. O(1) 时间插入、删除和获取随机元素 - 允许重复	困难	设计数据结构
284. 顶端迭代器	中等	迭代器设计
355. 设计推特	中等	设计
706. 设计哈希映射	简单	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/29278854