1206. 設計跳表 : 資料結構實作題

題目描述

這是 LeetCode 上的 ​​1206. 設計跳表​​ ，難度為 困難。

Tag : 「連結清單」、「資料結構」

不使用任何庫函數，設計一個 跳表 。

跳表 是在

例如，一個跳表包含 ​

​[30, 40, 50, 60, 70, 90]​

​​，然後增加 ​

​80​

​​、​

​45​

​ 到跳表中，以下圖的方式操作：

跳表中有很多層，每一層是一個短的連結清單。在第一層的作用下，增加、删除和搜尋操作的時間複雜度不超過 。跳表的每一個操作的平均時間複雜度是 ，空間複雜度是 。

在本題中，你的設計應該要包含這些函數：

• ​

  ​bool search(int target)​

  ​​: 傳回​

  ​target​

  ​ 是否存在于跳表中。
• ​

  ​void add(int num)​

  ​: 插入一個元素到跳表。
• ​

  ​bool erase(int num)​

  ​​: 在跳表中删除一個值，如果​

  ​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 已被擦除      

提示:

• 調用​

  ​search​

  ​​,​

  ​add​

  ​​,​

  ​erase​

  ​​ 操作次數不大于

資料結構

對于單連結清單而言，所有的操作（增删改查）都遵循「先查找，再操作」的步驟，這導緻在單連結清單上所有操作複雜度均為 （瓶頸在于查找過程）。

跳表相對于單連結清單，則是通過引入「多層」連結清單來優化查找過程，其中每層連結清單均是「有序」連結清單：

• 對于單連結清單的​

  ​Node​

  ​ 設計而言，我們隻需存儲對應的節點值 ​

  ​val​

  ​，以及目前節點的下一節點的指針 ​

  ​ne​

  ​ 即可（​

  ​ne​

  ​ 為一指針變量）
• 對于跳表來說，除了存儲對應的節點值​

  ​val​

  ​ 以外，我們需要存儲目前節點在「每一層」的下一節點指針 ​

  ​ne​

  ​（​

  ​ne​

  ​ 為指針數組）

跳表的 ​

​level​

​​ 編号從下往上遞增，最下層的連結清單為元素最全的有序單連結清單，而查找過程則是按照 ​

​level​

​ 從上往下進行。

操作次數的資料範圍為 ，是以設計最大的 ​​

​level​

​​ 為 即可確定複雜度，但由于操作次數 不可能全是 ​​

​add​

​​ 操作，是以這裡直接取 ​

​level​

​​ 為 。

同時為了簡化，建立一個哨兵節點 ​

​he​

​​，哨兵值的值應當足夠小（根據資料範圍，設定為 即可），所有的操作（假設目前操作的傳入值為 ​​

​t​

​），先進行統一化的查找：查找出每一層比 ​

​t​

​ 嚴格小的最後一個節點，将其存成 ​

​ns​

​ 數組。即 為 層嚴格比 小的最後一個節點。

再根據不同的操作進行下一步動作：

• ​

  ​search​

  ​​ 操作：由于最後一層必然是元素最全的單連結清單，是以可以直接通路​

  ​ns[0].ne[0]​

  ​​ 即是所有元素中滿足大于等于​

  ​t​

  ​​ 的第一個元素，通過判斷其值與傳入值​

  ​t​

  ​ 的大小關系來決定結果；
• ​

  ​add​

  ​ 操作：由于最後一層必然是元素最全的單連結清單，是以我們「從下往上」進行插入，最底下一層必然要插入，然後以一半的機率往上傳遞；
• ​

  ​erase​

  ​​ 操作：與​

  ​add​

  ​​ 操作互逆，按照「從下往上」的順序進行删除。需要注意的是，由于相同的值在跳表中可能存在多個，是以我們在「從下往上」删除過程中需要判斷待删除的元素與​

  ​ns[0].ne[0]​

  ​ 是否為同一進制素（即要判斷位址是否相同，而不是值相同）。

Java 代碼：

class Skiplist {
    int level = 10;
    class Node {
        int val;
        Node[] ne = new Node[level];
        Node (int _val) {
            val = _val;
        }
    }
    Random random = new Random();
    Node he = new Node(-1);
    void find(int {
        Node cur = he;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i];
            ns[i] = cur;
        }
    }
    public boolean search(int {
        Node[] ns = new Node[level];
        find(t, ns);
        return ns[0].ne[0] != null && ns[0].ne[0].val == t;
    }
    public void add(int {
        Node[] ns = new Node[level];
        find(t, ns);
        Node node = new Node(t);
        for (int i = 0; i < level; i++) {
            node.ne[i] = ns[i].ne[i];
            ns[i].ne[i] = node;
            if (random.nextInt(2) == 0) break;
        }
    }
    public boolean erase(int {
        Node[] ns = new Node[level];
        find(t, ns);
        Node node = ns[0].ne[0];
        if (node == null || node.val != t) return false;
        for (int i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i];
        return true;
    }
}      

TypeScript 代碼：

const level: number = 10
class TNode {
    val: number
    ne: TNode[] = new Array<TNode>(level)
    constructor(_val: number) {
        this.val = _val
    }
}
class Skiplist {
    he: TNode = new TNode(-1)
    find(t: number, ns: TNode[]): void {
        let cur = this.he
        for (let i = level - 1; i >= 0; i--) {
            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i]
            ns[i] = cur
        }
    }
    search(t: number): boolean {
        let ns: TNode[] = new Array<TNode>(level)
        this.find(t, ns)
        return ns[0].ne[0] != null && ns[0].ne[0].val == t
    }
    add(t: number): void {
        let ns: TNode[] = new Array<TNode>(level)
        this.find(t, ns)
        const node = new TNode(t)
        for (let i = 0; i < level; i++) {
            node.ne[i] = ns[i].ne[i]
            ns[i].ne[i] = node
            if (Math.round(Math.random()) == 0) break
        }
    }
    erase(t: number): boolean {
        let ns: TNode[] = new Array<TNode>(level)
        this.find(t, ns)
        const node = ns[0].ne[0]
        if (node == null || node.val != t) return false
        for (let i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i]
        return true      

• 時間複雜度：所有操作的複雜度瓶頸在于​

  ​find​

  ​​ 查找，​

  ​find​

  ​​ 查找期望複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.1206​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。