最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 二分查找 && 稀疏数组搜索 |刷题打卡

    正文概述 掘金(乐闻)   2021-04-08   97
    • 掘金团队号上线,助你 Offer 临门! 点击 查看详情

    一、题目描述

    面试题 10.05. 稀疏数组搜索
    
    稀疏数组搜索。有个排好序的字符串数组,其中散布着一些空字符串,编写一种方法,找出给定字符串的位置。
    
    示例1:
     输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
     输出:-1
     说明: 不存在返回-1。
    
    示例2:
     输入:words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
     输出:4
    提示:
    
    words的长度在[1, 1000000]之间
    

    二、思路分析

    从题目描述中给出了一个特定的条件排好序的字符串数组, 当我们看到排序好的数组题目时,我们优先考虑 二分查找 来解决。这道题也算是一道典型的 二分查找算法题。通过完成这道题,我希望读者朋友能掌握 二分查找 算法的基础步骤,文末附加 二分查找 的通用步骤模版。

    我们分析一下问题:一个数组中有一些 排好序 的字符串,而且字符串中间会夹杂着一些空字符串。

    我们可以设想一下,如果不考虑参杂的空字符串,让我们去查询某个具体的字符串的下标,是不是入门级别的一道二分查找算法题。那么假设如果没有参杂空字符串,我们应该怎么去解决这个道题呢?

    我将采用 TypeScript来解决这道题,ts 对比两个字符串的大小(ASCII码)可以直接通过 < > =去做比较。

    二分查找 && 稀疏数组搜索 |刷题打卡

    朋友们可以通过阅读注释来理解整个 二分查找 思路,相对来讲还是比较清晰的。

    不知道有没有朋友会有这样的想法:不就是在数组里面查找某个字符串的下标嘛,我直接遍历数组一个个的去对比不久得了,两行代码就搞定了,简单还好理解。

    但是我们想一下,直接遍历的情况下,我们需要对比每一个字符串,最坏的情况如果恰好目标字符串在数组的最后一位或者数组中根本没有目标字符串的时候,时间复杂度可是 O(N) 。 但是对于二分查找法,最坏的情况我们也只需要 logN次对比就能达到目的,这可是指数级别的差距。就比如数组中要是有1亿个字符串时,通过遍历对比,需要执行1亿次;而二分查找法只需要

    二分查找 && 稀疏数组搜索 |刷题打卡


    通过上面的分析我们已经知道了基础版 二分查找法 是怎么操作的了,那么回到最开始的问题,给到我们的字符串并不是单纯的排好序等着我们操作的数组,而是排序字符串数组中随机参杂了空字符串''。这些随机空字符串影响了数组字符串的下标,那么我们还能通过二分查找法来解决这道问题吗?

    答案是可以的。

    我们还是按照二分查找法通解方法作为主体,然后只要过滤掉特定的情况,比如 middle 字符串是空字符串时做一下特殊处理。

    				// 过滤范围中心字符串是空字符串的情况,
            // 因为是空字符串的话,我们不好做对比,就不能确定目标字符串到底是在中间偏左还是偏右
             if (words[i] !== s && words[middle] === '') {
                // 我们把范围稍微缩小一下,不管是改变起始位置还是结束位置,肯定会影响中间middle下标
                // 这里选择改变起始位置,当前你也可以 j--
                i++;
                // 记得要结束本轮循环,因为后面的比较没有任何意义
                continue;
            } else if (words[i] === s){
                // ⚠️!! 这个地方一定要注意,当我们缩小范围而且没有进行二分对比的话
                // 很有可能就把我们的目标字符串漏了,所以这里我们要做一下对比
                return i;
            }
    

    三、AC 代码

    二分查找 && 稀疏数组搜索 |刷题打卡

    二分查找 && 稀疏数组搜索 |刷题打卡

    四、总结

    对于排序数组,我们肯定是要优先考虑 二分查找法 来解决问题的,时间复杂度相对于遍历而言是指数级别的区别。

    二分查找法 代码都相似,我们可以总结出代码模板,面试时遇到这类题就直接一把梭。

    function findString(words: string[], s: string): number {
        // 首先定义查找的范围,初始化成数组的最大范围,即起始坐标与结尾坐标
        let i = 0;
        let j = words.length - 1;
        // 不断的缩小查找范围,直到搜索范围减小至 0
        while (i <= j) {
            // 取当前查询范围的中间值作为基准用于下方的判断
            let middle = Math.floor((i + j) / 2);
            // 二分查找通用步骤
            if (s > words[middle]) {
                // 如果目标字符串大于最中间的字符串,说明如果目标字符串存在的话,它肯定在中间位置的右边,
                // 那我们是不是就可以把搜索范围的起始位置变为中间位置
                i = middle + 1;
            } else if (s < words[middle]) {
                // 如果目标字符串小于最中间的字符串,说明如果目标字符串存在的话,它肯定在中间位置的左边,
                // 那我们是不是就可以把搜索范围的结束位置变为中间位置
                j = middle - 1;
            } else {
                // 恭喜,找到目标字符串了
                return middle;
            }
        }
        // 如果程序走到这里了,说明数组中并没有目标字符串,那么就返回 -1
        return -1;
    };
    

    起源地 » 二分查找 && 稀疏数组搜索 |刷题打卡

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元