mzoe666888

V1

2022/05/27阅读:24主题:兰青

内卷大厂系列《跳表》

大厂高频算法面试题:《跳表》,您将学到 跳表 是什么?解决什么问题?经常被面试官在Redis环节被问到,不要求能现场手撸出来,可以说明下 跳表 实现的具体思路和用到的数据结构模型。

一、跳表是什么

跳表(Skip List)思想上要比AVL、SB、红黑树等先进,但常数时间上有点飘。

数据的查询速度很快O(1),但是插入的速度比较慢O(N)

链表的插入速度快O(1),但是链表的查询速度比较慢O(N)

跳表的平均查找和插入时间复杂度都为O(logN),空间复杂度为O(N)

它是怎么做到增删改的时间复杂度也是O(logN)的?

采用多级单链表,由此可见消耗空间,正所谓时间和空间上的取舍。

核心思想如下

  • 第一层(最底层)上有N个节点,即所有节点都存在于第一层上
  • 高度随机决定,扔硬币问题,0.5的概率为正面,0.5的概率为反面,抛出正面则层数加一,即高度加一
  • 第一层有N个节点,第二层以0.5的概率扔硬币,所以第二层有N/2个,同理第三层有N/4,依次类推,所以当有N个节点的时候,形成跳表结构,需要logN次,跟输入规律没关系,跟概率有关系,但是概率问题也能logN,这点就NB了,是它先进的地方
  • 从最高层一次往下找,高链表上跨一个节点,底下不知道跨了多少个节点,这就是跳表的好处

二、跳表的功能

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

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计思想与链表相似。

例如,一个跳表包含 [30, 40, 50, 60, 70, 90] ,然后增加 80、45 到跳表中,以下图的方式操作:

跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n)),空间复杂度是 O(n)。

了解更多 : https://en.wikipedia.org/wiki/Skip_list

在本题中,你的设计应该要包含这些函数:

  • bool search(int target) : 返回target是否存在于跳表中。
  • void add(int num): 插入一个元素到跳表。
  • bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回false. 如果存在多个 num ,删除其中任意一个即可。

注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。呵呵呵!!!

示例:

输入
["Skiplist""add""add""add""search""add""search""erase""erase""search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[nullnullnullnullfalsenulltruefalsetruefalse]

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/design-skiplist
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

leetcode

三、跳表的实现

public class Skiplist {

    SkipListMap<Integer, Integer> skipListMap;

    public Skiplist() {
        this.skipListMap = new SkipListMap<>();
    }

    public boolean search(int target) {
        return skipListMap.containsKey(target);
    }

    public void add(int num) {
        skipListMap.put(num, num);
    }

    public boolean erase(int num) {
        if (!skipListMap.containsKey(num)) {
            return false;
        }
        skipListMap.remove(num);
        return true;
    }

    // 跳表的节点定义
    public static class SkipListNode<K extends Comparable<K>, V{
        public K key;
        public V val;
        public ArrayList<SkipListNode<K, V>> nextNodes;

        public SkipListNode(K k, V v) {
            key = k;
            val = v;
            nextNodes = new ArrayList<>();
        }

        // 遍历的时候,如果是往右遍历到的null(next == null), 遍历结束
        // 头(null), 头节点的null,认为最小
        // node  -> 头,node(null, "")  node.isKeyLess(!null)  true
        // node里面的key是否比otherKey小,true,不是false
        public boolean isKeyLess(K otherKey) {
            //  otherKey == null -> false
            return otherKey != null && (key == null || key.compareTo(otherKey) < 0);
        }

        public boolean isKeyEqual(K otherKey) {
            return (key == null && otherKey == null)
                    || (key != null && otherKey != null && key.compareTo(otherKey) == 0);
        }

    }

    public static class SkipListMap<K extends Comparable<K>, V{

        private static final double PROBABILITY = 0.5// < 0.5 继续做,>=0.5 停
        private SkipListNode<K, V> head;
        private int maxLevel;

        public SkipListMap() {
            head = new SkipListNode<>(nullnull);
            head.nextNodes.add(null); // 0
            maxLevel = 0;
        }

        // 从最高层开始,一路找下去,
        // 最终,找到第0层的<key的最右的节点
        private SkipListNode<K, V> mostRightLessNodeInTree(K key) {
            if (key == null) {
                return null;
            }
            int level = maxLevel;
            SkipListNode<K, V> cur = head;
            while (level >= 0) { // 从上层跳下层
                //  cur  level  -> level-1
                cur = mostRightLessNodeInLevel(key, cur, level--);
            }
            return cur;
        }

        // 在level层里,如何往右移动
        // 现在来到的节点是cur,来到了cur的level层,在level层上,找到<key最后一个节点并返回
        private SkipListNode<K, V> mostRightLessNodeInLevel(K key,
                                                            SkipListNode<K, V> cur,
                                                            int level)
 
{
            SkipListNode<K, V> next = cur.nextNodes.get(level);
            while (next != null && next.isKeyLess(key)) {
                cur = next;
                next = cur.nextNodes.get(level);
            }
            return cur;
        }

        public boolean containsKey(K key) {
            if (key == null) {
                return false;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = less.nextNodes.get(0);
            return next != null && next.isKeyEqual(key);
        }

        // 新增、改value
        public void put(K key, V value) {
            if (key == null) {
                return;
            }
            // 0层上,最右一个,< key 的Node -> >key
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> find = less.nextNodes.get(0);
            if (find != null && find.isKeyEqual(key)) {
                // find.val = value;
                // 处理重复值问题,如果没有不允许重复,直接更新value即可,下边三行代码可以不写
                SkipListNode<K, V> newNode = new SkipListNode<>(key, value);
                newNode.nextNodes.add(find.nextNodes.get(0));
                find.nextNodes.set(0, newNode);
            } else { // find == null   8   7   9
                int newNodeLevel = 0;
                while (Math.random() < PROBABILITY) {
                    newNodeLevel++;
                }
                // newNodeLevel
                while (newNodeLevel > maxLevel) {
                    head.nextNodes.add(null);
                    maxLevel++;
                }
                SkipListNode<K, V> newNode = new SkipListNode<>(key, value);
                for (int i = 0; i <= newNodeLevel; i++) {
                    newNode.nextNodes.add(null);
                }
                int level = maxLevel;
                SkipListNode<K, V> pre = head;
                while (level >= 0) {
                    // level 层中,找到最右的 < key 的节点
                    pre = mostRightLessNodeInLevel(key, pre, level);
                    if (level <= newNodeLevel) {
                        newNode.nextNodes.set(level, pre.nextNodes.get(level));
                        pre.nextNodes.set(level, newNode);
                    }
                    level--;
                }
            }
        }

        public V get(K key) {
            if (key == null) {
                return null;
            }
            SkipListNode<K, V> less = mostRightLessNodeInTree(key);
            SkipListNode<K, V> next = less.nextNodes.get(0);
            return next != null && next.isKeyEqual(key) ? next.val : null;
        }

        public void remove(K key) {
            if (containsKey(key)) {
                int level = maxLevel;
                SkipListNode<K, V> pre = head;
                while (level >= 0) {
                    pre = mostRightLessNodeInLevel(key, pre, level);
                    SkipListNode<K, V> next = pre.nextNodes.get(level);
                    // 1)在这一层中,pre下一个就是key
                    // 2)在这一层中,pre的下一个key是>要删除key
                    if (next != null && next.isKeyEqual(key)) {
                        // free delete node memory -> C++
                        // level : pre -> next(key) -> ...
                        pre.nextNodes.set(level, next.nextNodes.get(level));
                    }
                    // 在level层只有一个节点了,就是默认节点head
                    if (level != 0 && pre == head && pre.nextNodes.get(level) == null) {
                        head.nextNodes.remove(level);
                        maxLevel--;
                    }
                    level--;
                }
            }
        }
    }
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1