V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
kensoz
V2EX  ›  前端开发

js 有什么优雅的方式判断一组数组内数字是否连续

  •  1
     
  •   kensoz · 2021-10-11 09:28:13 +08:00 · 3454 次点击
    这是一个创建于 1125 天前的主题,其中的信息可能已经有所发展或是发生改变。

    比如有一个数组:let arr = [1,2,3,4,5,7]

    可见数组中数字不连续,而且没有 6

    有没有什么优雅的方式或者奇淫技巧可以判断这个数组不连续并且缺少 6

    目前的做法就是先声明一个为 0 的变量然后循环数组,比较的同时变量自增,不知道各位有没有什么好的办法

    第 1 条附言  ·  2021-10-11 11:34:54 +08:00
    附言:
    这个数组是有序的
    这个数组可能不缺[1,2,3,4,5]
    也可能缺 1 个[1,2,3,5]
    也可能缺多个[1,2,5]
    也可能在多个地方缺[3,5]

    看来是我的题目有点误导性,应该是判断是否连续后找到缺失项
    30 条回复    2021-10-12 00:40:53 +08:00
    2kCS5c0b0ITXE5k2
        1
    2kCS5c0b0ITXE5k2  
       2021-10-11 09:36:01 +08:00   ❤️ 1
    循环. 连变量都不需要声明.
    iMusic
        2
    iMusic  
       2021-10-11 09:36:57 +08:00   ❤️ 1
    如果只是单纯判断是否连续,可以把最后一项减去第一项,和数组的 length + 1 对比
    rrfeng
        3
    rrfeng  
       2021-10-11 09:42:44 +08:00 via Android   ❤️ 1
    先快速判断 max - min == len + 1
    如果满足然后再遍历。
    AoEiuV020
        4
    AoEiuV020  
       2021-10-11 09:46:17 +08:00   ❤️ 1
    本质上一样,但这里要奇淫技巧就是 reduce 了,

    var loss
    arr.reduce((prev,cur) => {
    console.log("" + prev + ", " + cur)
    if (prev == undefined) {
    return undefined
    }
    if(cur - prev == 1) {
    return cur
    } else {
    loss = prev + 1
    }

    })
    console.log(loss)
    aureole999
        5
    aureole999  
       2021-10-11 10:03:12 +08:00 via iPhone   ❤️ 1
    二分查找,如果 index 对应是值是 index+2 的就向左找,是 index+1 的就往右找
    mxT52CRuqR6o5
        6
    mxT52CRuqR6o5  
       2021-10-11 10:08:34 +08:00 via Android   ❤️ 1
    你用啥方法也都是 O(n)级别的
    ipwx
        7
    ipwx  
       2021-10-11 10:12:33 +08:00   ❤️ 1
    你得加附加条件。如果这个数组是有序的,那么 O(1) 查看一下首尾就行。不然就要 O(n) 扫一遍
    Yumwey
        8
    Yumwey  
       2021-10-11 10:13:03 +08:00   ❤️ 1
    等差数列
    huang119412
        9
    huang119412  
       2021-10-11 10:13:53 +08:00   ❤️ 1
    @aureole999 @mxT52CRuqR6o5 这应该是 LeetCode 的题目吧,应该有个前提是有序的,这样就可以用二分法查找。
    anguiao
        10
    anguiao  
       2021-10-11 10:18:19 +08:00   ❤️ 1
    只想知道连不连续,那首尾相减判断一下就行了。
    如果想知道缺哪个数字的话,可以用二分查找。
    iDontEatCookie
        11
    iDontEatCookie  
       2021-10-11 10:32:42 +08:00   ❤️ 1
    let index = arr.findIndex((cur, index, arr) => cur - arr[0] !== index)
    if (index !== -1) {
    console.log(arr[0] + index)
    }
    aureole999
        12
    aureole999  
       2021-10-11 10:36:04 +08:00   ❤️ 1
    @huang119412 他说设个变量是 0 然后边比较边自增,那应该是有序。当然其它条件他也没说,比如是不是只缺一个数字
    otakustay
        13
    otakustay  
       2021-10-11 10:37:04 +08:00   ❤️ 1
    @anguiao 不能吧,[1, 1, 3]首尾相减就是对的,但它不连续
    mxT52CRuqR6o5
        14
    mxT52CRuqR6o5  
       2021-10-11 10:47:50 +08:00   ❤️ 1
    @huang119412
    干脆我们假定这个的数组内数字是连续的,这样我们就不需要检查就能知道这个数组是符合条件的了,这样时间复杂度就为 O(0)
    Biwood
        15
    Biwood  
       2021-10-11 10:53:34 +08:00   ❤️ 1
    const isIncremental = arr => arr.every((item, index, arr) => (index > 0 ? item - arr[index-1] === 1 : true))

    isIncremental([1,2,3,4,5,7]) // false
    KouShuiYu
        16
    KouShuiYu  
       2021-10-11 11:01:13 +08:00   ❤️ 1
    应该是最优雅的
    [1,2,3].every((ele,index, arr) => (ele - arr[index-1]) === 1 || index === 0)
    Biwood
        17
    Biwood  
       2021-10-11 11:02:48 +08:00   ❤️ 1
    好吧,没看到要找出缺少项,那就扩充一下

    const isIncremental = arr => arr.reduce((prev, item, index, arr) => {
    if (index === 0) return true;
    if (prev !== true) return prev;
    return item - arr[index-1] === 1 ? true : arr[index-1] + 1;
    }, true)

    isIncremental([1,2,3,4])
    // true

    isIncremental([1,2,3,4,5,7])
    // 6
    kensoz
        18
    kensoz  
    OP
       2021-10-11 11:16:37 +08:00
    @huang119412
    @aureole999
    @ipwx
    不好意思各位,这个数组理论上是有序的,
    业务场景可以想象成从数据库某表里取得的 id,id 对应所在行,先确认这一组 id 是否连续,不连续就找到缺失的数字
    kensoz
        19
    kensoz  
    OP
       2021-10-11 11:28:01 +08:00
    @aureole999
    这个数组可能不缺[1,2,3,4,5]
    也可能缺 1 个[1,2,3,5]
    也可能缺多个[1,2,5]
    也可能在多个地方缺[3,5]
    chairuosen
        20
    chairuosen  
       2021-10-11 11:49:48 +08:00
    return arr.length - 1 === arr[arr.length-1] - arr[0]
    O(1) 啊
    aureole999
        21
    aureole999  
       2021-10-11 12:38:55 +08:00
    @kensoz 无重复的话可以先判断首尾相减+1 是否等于长度,等于的话就说明从数组开始的地方不缺,再判断一下第一个是不是 1,就不用往下走了。差 1 的话只缺一个,二分解决。差 2 以上的话数组再分一半,左右之间挨着的两个判断一下,然后左右递归,分别判断。速度最好 O(logn),最差 O(n)。边界需要处理好。
    aureole999
        22
    aureole999  
       2021-10-11 13:11:32 +08:00
    递归
    var a = [3,5,6,7,9,10,22];
    var res = [];
    if (a[0] > 1) {
    res = Array.from({length: a[0]-1}, (_, i) => i + 1);
    }
    res.push(...find(a, 0, a.length-1));


    function find(arr, start, end) {

    if (arr[end] - arr[start] == end - start) {
    return [];
    }
    if (start >= end) return [];

    var mid = Math.floor((end + start) / 2);
    var res = [];

    res.push(...find(arr, start, mid));
    if (arr[mid] + 1 != arr[mid+1]) {
    var max = arr[mid+1] - 1;
    var min = arr[mid] + 1;
    res.push(...Array.from({length: max-min+1}, (_, i) => i + min));
    }
    res.push(...find(arr, mid + 1, end));
    return res;
    }

    console.log(res);
    icedwatermelon
        23
    icedwatermelon  
       2021-10-11 13:38:25 +08:00
    [...Array(arr[arr.length-1])].map((v, i) => (i+1)).filter((v,i)=>(!arr.includes(v)))
    wanguorui123
        24
    wanguorui123  
       2021-10-11 14:16:05 +08:00
    [1,2,3,4,5,6].sort().every((v,i,arr)=>i>0?arr[i-1]+1==v:true)
    mxT52CRuqR6o5
        25
    mxT52CRuqR6o5  
       2021-10-11 14:16:24 +08:00
    @kensoz 能保证从 1 开始吗?如果不能的话,如果缺的是两边的话是判断不出来的
    wanguorui123
        26
    wanguorui123  
       2021-10-11 14:17:52 +08:00
    @wanguorui123 [1,2,3,4,5,6].every((v,i,arr)=>i>0?arr[i-1]+1==v:true)
    mxT52CRuqR6o5
        27
    mxT52CRuqR6o5  
       2021-10-11 14:32:50 +08:00
    @kensoz
    开头的数字不能确定,则无法判断出头部数字的缺失,尾部的数字如果不能确定,则无法判断出尾部数字的缺失
    kensoz
        28
    kensoz  
    OP
       2021-10-11 15:08:28 +08:00
    @mxT52CRuqR6o5
    用场景来举例就是一个表,记录一个东西并用 id 编号。
    增加了 1,2,3id 后,删除了 2id,查询得目前剩下 1,3id,如果再有新增就用 2 来编号(最小的缺失数)
    但是这个删除行为是随机的,不可控,所以理论上任何位数都有可能被删除
    不过可以保证的是这一定是一个有序数组

    ps:如果是后端直接用 sql 查询空位即可,但是数据交给前端处理的话,就相对麻烦了一下
    mxT52CRuqR6o5
        29
    mxT52CRuqR6o5  
       2021-10-11 15:27:30 +08:00
    @kensoz
    那我第一要考虑的就是“最小的缺失数”这个需求到底合不合理,最优先考虑是去否掉这个需求
    lrvinye
        30
    lrvinye  
       2021-10-12 00:40:53 +08:00 via iPhone
    @iMusic 中间的不管了? 随手举个例子 [1,6,4,9,5]
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1053 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:15 · PVG 07:15 · LAX 15:15 · JFK 18:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.