题解 | #牛牛的跳表设计#

import java.util.*;


public class Solution {
    public static int max_deep = 10;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operations int整型二维数组
     * @param data int整型二维数组
     * @return bool布尔型一维数组
     */
    class NodeT {
        private NodeT down;
        private NodeT pro;
        private NodeT next;
        private int val;

        public NodeT (int val) {
            this.val = val;
        }

        public NodeT () {
        }

        public NodeT (int val, NodeT down, NodeT pro, NodeT next) {
            this.val = val;
            this.down = down;
            this.pro = pro;
            this.next = next;
        }

//        @Override
//        public  String toString(){
//
//            return this.val + ";" +this.next.val +  ";" +this.down.val;
//        }
    }
    
    class Skiplist {
        NodeT node;
        public Skiplist() {
            this.node = new NodeT(-1);
            //第一个节点建立10级索引,
            int k = max_deep;
            NodeT temp = node;
            while (k > 0) {
                temp.down = new NodeT(-1);
                temp = temp.down;
                k--;
            }

        };
        boolean search(int target) {
            NodeT temp = node;
            while (temp != null) {
                while (temp.next != null && temp.next.val < target) {
                    temp = temp.next;
                }
                if (temp.val == target || (temp.next != null && temp.next.val == target)) return true;
                temp = temp.down;
            }
            return false;
        }; // 返回target是否存在于跳表中。

        void add(int num) {
            //随机生成0-10级索引,
            int k = new Random().nextInt(max_deep);
            NodeT temp = node;
            int index = max_deep;
            NodeT tp = null;
            while (index >= 0) {
                while (temp.next != null && temp.next.val < num) {
                    temp = temp.next;
                }
                if (index <= k) {
                    //插入索引
                    NodeT nodet = new NodeT(num);
                    nodet.next = temp.next;
                    if (temp.next != null) temp.next.pro = nodet;
                    nodet.pro = temp;
                    temp.next = nodet;

                    if (tp != null) tp.down = nodet;
                    tp = nodet;
                }
                temp = temp.down;
                index--;
            }
        }; // 插入一个元素到跳表。 插入成功输出true
        boolean erase(int num) {
            //找到后后面的k级索引都要删除
            NodeT temp = node;
            boolean flag = false;
            while (temp != null) {
                while (temp.next != null && temp.next.val < num) {
                    temp = temp.next;
                }
                if(temp.next != null && temp.next.val == num) {
                    temp = temp.next;
                }
                if (temp.val == num) {
                    //删除第k级索引
                    flag = true;
                    temp.pro.next = temp.next;
                }
                temp = temp.down;
            }
            return flag;
        };// 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
    };
    public boolean[] performOperations (int[][] operations, int[][] data) {
        List<Boolean> list = new ArrayList<>();
        Skiplist skiplist = new Skiplist();
        for (int i = 0; i < operations.length; i++) {
            if (operations[i][0] == 0) {
                list.add(skiplist.search(data[i][0]));
            } else if (operations[i][0] == 1) {
                skiplist.add(data[i][0]);
                list.add(true);  // add 操作返回 true
            } else if (operations[i][0] == 2) {
                list.add(skiplist.erase(data[i][0]));
            }
        }
        boolean[] res = new boolean[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;// write code here
    }
}