leetcode 1206 设计跳表java实现

本文主要是介绍leetcode 1206 设计跳表java实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

跳表是在 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 ，删除其中任意一个即可。

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

解题思路

初始化

初始化时，需要给提供一个所有层数的前缀节点，同时头节点指向顶层的前缀节点。

查询

查询比较简单，按照从上到下的方法判断就好。

删除

找到每层对应值的左侧最近节点，然后修改指针。

插入

通过记录每层左侧最近的节点，然后从底层向上，依次拿出左侧节点列表中的节点，在节点后面添加新元素节点，同时，新元素的层数通过随机数判断获取。

public class Skiplist {


        private SkipNode head;

        /**
         * 初始化构建
         */
        public Skiplist() {
            head = null;
            // 这里需要构建每层链表的最左侧节点，head指向最顶层最左侧节点
            for (int i = 0; i < 16; i++) {
                SkipNode node = new SkipNode(0);
                node.down = head;
                head = node;
            }
        }

    /**
     * 搜索
     * @param target 目标值
     * @return 是否存在目标值
     */
    public boolean search(int target) {
            SkipNode h = head;
            // 遍历知道最底层
            while (h != null) {
                if (h.right != null && h.right.val == target) {
                    return true;
                }
                // 如果遍历到最右侧节点或者当前节点是小于目标值的最后一个节点，遍历下一层
                if (h.right == null || h.right.val > target) {
                    h = h.down;
                } else {
                    h = h.right;
                }
            }
            return false;
        }

    /**
     * 添加节点
     * @param num 值
     */
    public void add(int num) {
            SkipNode h = head;
            // 保存每次往下层遍历时的节点，往下遍历，代表该节点时目标值可能存放位置的左侧节点
            List<SkipNode> downList = new ArrayList<>();
            while (h != null) {
                if (h.right == null || h.right.val >= num) {
                    // 这里按照先进先出的存法（也可以使用队列
                    downList.add(0, h);
                    h = h.down;
                } else {
                    h = h.right;
                }
            }
            SkipNode d = null;
            // 根据之前保存的集合，从底层开始一层层往上添加
            for (int i = 0; i <= downList.size(); i++) {
                SkipNode node = new SkipNode(num);
                node.down = d;
                node.right = downList.get(i).right;
                downList.get(i).right = node;
                d = node;

                // 概率问题
                if(Math.random() < 0.5) {
                    break;
                }
            }
        }

    /**
     * 删除某个值
     * @param num 值
     * @return 是否删除成功
     */
    public boolean erase(int num) {
            SkipNode h = head;
            boolean flag = false;
            while (h != null) {
                if (h.right == null || h.right.val > num) {
                    h = h.down;
                } else if (h.right.val == num) {
                    h.right = h.right.right;
                    flag = true;
                    h = h.down;
                } else {
                    h = h.right;
                }
            }
            return flag;
        }


    class SkipNode{
        int val;

        SkipNode right,down;

        public SkipNode(int val) {
            this.val = val;
            right = null;
            down = null;
        }
    }


}

下面是网上提供的另一种实现方案

不同点：

• 通过数组的形式来表示层级关系；
• 增加了实际层数（当前最大层）变量，每次都从实际层数开始，而不从最顶层。
• 随机层数算法不同。

class Skiplist {
    /**
     * 最大层数
     */
    private static int DEFAULT_MAX_LEVEL = 32;
    /**
     * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
     */
    private static double DEFAULT_P_FACTOR = 0.25;

    Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

    int currentLevel = 1; //表示当前nodes的实际层数，它从1开始


    public Skiplist() {
    }

    public boolean search(int target) {
        Node searchNode = head;
        for (int i = currentLevel-1; i >=0; i--) {
            searchNode = findClosest(searchNode, i, target);
            if (searchNode.next[i]!=null && searchNode.next[i].value == target){
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @param num
     */
    public void add(int num) {
        int level = randomLevel();
        Node updateNode = head;
        Node newNode = new Node(num,level);
        // 计算出当前num 索引的实际层数，从该层开始添加索引
        for (int i = currentLevel-1; i>=0; i--) {
            //找到本层最近离num最近的list
            updateNode = findClosest(updateNode,i,num);
            if (i<level){
                if (updateNode.next[i]==null){
                    updateNode.next[i] = newNode;
                }else{
                    Node temp = updateNode.next[i];
                    updateNode.next[i] = newNode;
                    newNode.next[i] = temp;
                }
            }
        }
        if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
            for (int i = currentLevel; i < level; i++) {
                head.next[i] = newNode;
            }
            currentLevel = level;
        }

    }

    public boolean erase(int num) {
        boolean flag = false;
        Node searchNode = head;
        for (int i = currentLevel-1; i >=0; i--) {
            searchNode = findClosest(searchNode, i, num);
            if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                //找到该层中该节点
                searchNode.next[i] = searchNode.next[i].next[i];
                flag = true;
                continue;
            }
        }
        return flag;
    }

    /**
     * 找到level层 value 大于node 的节点
     * @param node
     * @param levelIndex
     * @param value
     * @return
     */
    private Node findClosest(Node node,int levelIndex,int value){
        while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
            node = node.next[levelIndex];
        }
        return node;
    }


    /**
     * 随机一个层数
     */
    private static int randomLevel(){
        int level = 1;
        while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
            level ++ ;
        }
        return level;
    }


    class Node{
        Integer value;
        Node[] next;

        public Node(Integer value,int size) {
            this.value = value;
            this.next = new Node[size];
        }

        @Override
        public String toString() {
            return String.valueOf(value);
        }
    }

}

这篇关于leetcode 1206 设计跳表java实现的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！