LeetCode 1206. Design Skiplist

原题链接在这里：https://leetcode.com/problems/design-skiplist/description/

题目：

Design a Skiplist without using any built-in libraries.

A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists.

For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:

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

You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).

See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list

Implement the Skiplist class:

• Skiplist() Initializes the object of the skiplist.
• bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise.
• void add(int num) Inserts the value num into the SkipList.
• bool erase(int num) Removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine.

Note that duplicates may exist in the Skiplist, your code needs to handle this situation.

Example 1:

Input
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
Output
[null, null, null, null, false, null, true, false, true, false]Explanation
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // return False
skiplist.add(4);
skiplist.search(1); // return True
skiplist.erase(0);  // return False, 0 is not in skiplist.
skiplist.erase(1);  // return True
skiplist.search(1); // return False, 1 has already been erased.

Constraints:

• 0 <= num, target <= 2 * 104
• At most 5 * 104 calls will be made to search, add, and erase.

题解：

The skiplist is multiple layers of linked lists. Each layer list skips over a subset of the elements in the list below it.

We begin with Node class containing value, next pointed node, down pointed node. next is the same as regular list. down is pointing to a copy node having the same value in the below layer list.

When adding node, create a stack to keep track of the path taken during the search. As we may need to insert new value at multiple layers. This stack is used when we track back and decide if we need to add a copy node after these tranversed layers.

Traverse starting from the head of topmost list.

Move right until finding a node whose next value is greater than the target.
Then move down one level and repeat the process.
Now we hit the bottom laywer and find the right position. In sert the value and traverse back up with a 50% chance of inserting it into above levels.

If at the top level, and insert is still true, we add a new level on the top.

Search and erase are similar.

Time Complexity: search, O(long). add, O(logn). erase, O(logn). Ideally at each layer above, there is half less nodes. The height of the laywers is logn.

Space: O(n). n is the number of nodes at the bottom laywer. Each layer up has one half nodes. n + n/2 + n/4 +... < 2n.

AC Java:

class Skiplist {
    Node head;
    Random rand;

    public Skiplist() {
        head = new Node(-1, null, null);
        rand = new Random();
    }
    
    public boolean search(int target) {
        Node cur = head;
        while(cur != null){
            while(cur.next != null && cur.next.val < target){
                cur = cur.next;
            }
            if(cur.next != null && cur.next.val == target){
                return true;
            }

            cur = cur.down;
        }

        return false;
    }
    
    public void add(int num) {
        Node cur = head;
        Stack<Node> stk = new Stack<>();
        while(cur != null){
            while(cur.next != null && cur.next.val < num){
                cur = cur.next;
            }
            stk.push(cur);
            cur = cur.down;
        }

        boolean insert = true;
        Node down = null;
        while(insert && !stk.isEmpty()){
            cur = stk.pop();
            cur.next = new Node(num, cur.next, down);
            down = cur.next;
            insert = rand.nextDouble() < 0.5;
        }

        if(insert){
            head = new Node(-1, null, head);
        }
    }
    
    public boolean erase(int num) {
        Node cur = head;
        boolean found = false;
        while(cur != null){
            while(cur.next != null && cur.next.val < num){
                cur = cur.next;
            }

            if(cur.next != null && cur.next.val == num){
                found = true;
                cur.next = cur.next.next;
            }

            cur = cur.down;
        }

        return found;
    }
}

class Node{
    int val;
    Node next;
    Node down;
    public Node(int val, Node next, Node down){
        this.val = val;
        this.next = next;
        this.down = down;
    }
}

/**
 * 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);
 */

类似Design Linked List.