首页 > 其他分享 >如何用 30s 给面试官讲清楚跳表

如何用 30s 给面试官讲清楚跳表

时间:2022-12-15 11:11:59浏览次数:66  
标签:链表 面试官 元素 插入 30s 查找 索引 跳表

查找

假设有如下这样一个有序链表:

想要查找 24、43、59,按照顺序遍历,分别需要比较的次数为 2、4、6

目前查找的时间复杂度是 O(N),如何提高查找效率?

很容易想到二分查找,将查找的时间复杂度降到 O(LogN)

具体来说,我们把链表中的一些节点提取出来,作为索引,类似于二叉搜索树,得到如下结构:

这里我们把 10、30、50、80 提取出来作为一级索引,这样搜索的时候就可以使用二分查找来减少比较次数了。

我们还可以再从一级索引提取一些元素出来,作为二级索引,变成如下结构:

比如如果想要查找 59,那么搜索路径就是下面这样的:

回顾下链表的定义:

class ListNode {
    private int val;
	private ListNode next;
    
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

我们在每一个节点的基础上添加一个 down 指针,用来指向下一层的节点

class Node {
    private int val;
	private ListNode next;
    private ListNode down;
    
    public ListNode(int val) {
        this.val = val;
        this.next = null;
        this.down = null;
    }
}

这样,一个最简单的跳表节点就定义出来了。

我们这里说的只是最简单的实现,像比如 Redis 的跳表实现和我们说的还是有所不同的,当然了,思想都是一致的

所以跳表是什么?简单来说,跳表就是支持二分查找的有序链表

具体的搜索算法如下:

/* 如果存在 x, 返回 x 所在的节点, 否则返回 x 的后继节点 */  
private Node find(x)  {  
    p = top;  
    while (true) {  
        while (p.next.val < x){
            p = p.next;
        }
        if (p.down == null){
            return p.next;  
        }
        p = p.down;  
    }
    return null;
}

插入

关于插入,大家可能很容易想到往最下面一层的有序链表中添加数据,但是索引该咋办?索引要不要更新呢?

如果不更新索引,就可能出现两个索引节点之间数据非常多的情况,极端情况下跳表就会退化为单链表,从而使得查找效率从 O(LogN) 退化为 O(N)。

所以,我们在插入数据的时候,索引节点也需要相应的改变来避免查找效率的退化

比较容易想到的做法就是完全重建索引,我们每次插入数据后,都把这个跳表的索引删掉全部重建。因为索引的空间复杂度是 O(N),即:索引节点的个数是 O(N) 级别,每次完全重新建一个 O(N) 级别的索引,时间复杂度也是 O(N) 。造成的后果是:为了维护索引,导致每次插入数据的时间复杂度变成了 O(N)。

那有没有其他效率比较高的方式来维护索引呢?

最理想的索引就是在原始链表中每隔一个元素抽取一个元素做为一级索引。换种说法,我们在原始链表中【随机】的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢?

当然可以,因为一般随机选的元素相对来说都是比较均匀的。如下图所示,随机选择了 n/2 个元素做为一级索引,虽然不是每隔一个元素抽取一个,但是对于查找效率来讲,影响不大,比如我们想找元素 16,仍然可以通过一级索引,使得遍历路径较少了将近一半。

当然了,如果抽取的一级索引的元素恰好是前一半的元素 1、3、4、5、7、8,那么查找效率确实没有提升,但是这样的概率太小了。所以我们可以认为:当原始链表中元素数量足够大,且抽取足够随机的话,我们得到的索引是均匀的。所以,我们可以维护一个这样的索引:随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引,依次类推,一直到最顶层索引。这里每层索引的元素个数已经确定,且每层索引元素选取的足够随机,所以可以通过索引来提升跳表的查找效率。

那代码具体该如何实现,使得在每次新插入元素的时候,尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引....呢?

其实很简单啦,搞一个概率算法就行了(具体是怎么个概率法这里就不详细解释了),当每次有数据要插入时,先通过概率算法告诉我们这个元素需要插入到几级索引中,然后开始维护索引并把数据插入到原始链表中。

如下所示,插入新元素 12,假设概率算法返回的结果是 4,表示新元素需要插入到 4 级索引中,同时,我们还需要建立 3 级索引、2 级索引和 1 级索引(也就是原始有序链表)

那插入数据时维护索引的时间复杂度是多少呢?

跳表中,每一层索引都是一个有序的单链表,元素插入到单链表的时间复杂度为 O(1),我们索引的高度最多为 LogN,当插入一个元素 x 时,最坏的情况就是元素 x 需要插入到每层索引中,所以插入数据的最坏时间复杂度是 O(LogN),最好的时间复杂度是 O(1)。

删除

跳表删除数据时,要把索引中对应节点也要删掉。如下图所示,如果要删除元素 8,需要把原始链表中的 8 和第 2、3 级索引的 8 都删除掉。

删除元素的过程跟查找元素的过程类似,只不过在查找的路径上如果发现了要删除的元素 x,则执行删除操作。

跳表中,每一层索引都是一个有序的单链表,单链表删除元素的时间复杂度为 O(1),最多需要删除 LogN 个元素(索引层数为 LogN),所以删除元素的总时间包 = 查找元素的时间 + 删除 LogN 个元素的时间 = O(LogN ) + O(LogN ) = 2O(LogN ),忽略常数部分,删除元素的时间复杂度为 O(LogN)。

小伙伴们大家好呀,本文首发于公众号@飞天小牛肉,阿里云 & InfoQ 签约作者,分享大厂面试原创高质量题解、原创技术干活和成长经验~

标签:链表,面试官,元素,插入,30s,查找,索引,跳表
From: https://www.cnblogs.com/cswiki/p/16984525.html

相关文章

  • redis反杀面试官之10问
    简言1.笔者近几年来一直使用redis,也对redis有过仔细的研究,不敢说精通,熟悉至少是有的2.redis越来越火,网上相应的文章,总结,面试问题也有很多,但大多是应付简单面试用的,如果面......
  • 面试官问上一家公司离职原因怎么办?
    跳槽目的跳槽的目的,应该是加薪、晋级、换行,理论上三者都占才好,实际中只要有一个能满足,就算成功跳槽企业要求要求“本科学历,3年以上相关岗位工作经验”,请问这3年以上的工作经......
  • 面试官本拿求素数搞我,但被我优雅的“回击“了(素数筛)
    前言现在的面试官,是无数开发者的梦魇,能够吊打面试官的属实不多,因为大部分面试官真的有那么那几下子。但在面试中,我们这些小生存者不能全盘否定只能单点突破—从某个问题上......
  • 2022-12-30Spring-1
    1.静态资源配置原理SpringBoot启动默认加载xxxAutoConfiguration类(自动配置类)。SpringMVC功能的自动配置类WebMvcAutoConfiguration生效,给容器中配置了什么。配置文件......
  • ‍面试官:工作两年了,这么简单的算法题你都不会?
    技术推荐1、前端技术导航大全推荐:★★★★★地址:​​前端技术导航大全​​2、前端面试题库推荐:★★★★★地址:前端面试题库3、开发者颜色值转换工具推荐:★★★★★地址:开发......
  • 【面试】如果你这样回答“什么是线程安全”,面试官都会对你刮目相看
    有读者跟我说,喜欢看我的文章,说很容易读,我确实在易读性上花费的心思不亚于在内容上。因为我不喜欢一上来就堆很多东西,而且把简单的东西搞得复杂人人都会,但是把复杂的东西讲......
  • LevelDB源码剖析(3) Skiplist跳表
    1.背景什么是跳表?跳表是SortedMap的一种具体实现,是一种概率性的数据结构。跳表拥有SortedMap的所有功能,定位和红黑树类似,其和红黑树的区别在于优点:跳表的实现更加简单......
  • 面试官:介绍一下 Redis 三种集群模式
    小码今天去面试。面试官:给我介绍一下Redis集群,小码:啊,平时开发用的都是单机Redis,没怎么用过集群了。面试官:好的,出门右转不谢。小码内心困惑:在小公司业务量也不大,单机的......
  • 【面试题】 面试官为啥总是喜欢问前端路由实现方式?
    背景从事前端开发的同学,在实际工作中,一定会接触过路由这个概念,同时在面试的过程中,经常会被问及关于前端路由的实现方式,面试官到底想考察什么?在现在SPA单页面模式盛行,前后端......
  • 面试官问:为什么kafka这么快,又能保证消息不丢失?
    小菜鸡最近在疯狂面试中,就是为了能拿到一份满意的offer,这不上周又去头条受虐了。面试过程中,由于小菜鸡的充分准备(letcode各种刷),各种算法题不在话下,顺利的通过的头条变态的算......