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

[kensoz]

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

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

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

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

附言：
这个数组是有序的
这个数组可能不缺[1,2,3,4,5]
也可能缺 1 个[1,2,3,5]
也可能缺多个[1,2,5]
也可能在多个地方缺[3,5]

看来是我的题目有点误导性，应该是判断是否连续后找到缺失项

[2kCS5c0b0ITXE5k2]

循环. 连变量都不需要声明.

[iMusic]

如果只是单纯判断是否连续，可以把最后一项减去第一项，和数组的 length + 1 对比

[rrfeng]

先快速判断 max - min == len + 1
如果满足然后再遍历。

[AoEiuV020]

本质上一样，但这里要奇淫技巧就是 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]

二分查找，如果 index 对应是值是 index+2 的就向左找，是 index+1 的就往右找

[mxT52CRuqR6o5]

你用啥方法也都是 O(n)级别的

[ipwx]

你得加附加条件。如果这个数组是有序的，那么 O(1) 查看一下首尾就行。不然就要 O(n) 扫一遍

[Yumwey]

等差数列

[huang119412]

@aureole999 @mxT52CRuqR6o5 这应该是 LeetCode 的题目吧，应该有个前提是有序的，这样就可以用二分法查找。

[anguiao]

只想知道连不连续，那首尾相减判断一下就行了。
如果想知道缺哪个数字的话，可以用二分查找。

[iDontEatCookie]

let index = arr.findIndex((cur, index, arr) => cur - arr[0] !== index)
if (index !== -1) {
console.log(arr[0] + index)
}

[aureole999]

@huang119412 他说设个变量是 0 然后边比较边自增，那应该是有序。当然其它条件他也没说，比如是不是只缺一个数字

[otakustay]

@anguiao 不能吧，[1, 1, 3]首尾相减就是对的，但它不连续

[mxT52CRuqR6o5]

@huang119412
干脆我们假定这个的数组内数字是连续的，这样我们就不需要检查就能知道这个数组是符合条件的了，这样时间复杂度就为 O(0)

[Biwood]

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]

应该是最优雅的
[1,2,3].every((ele,index, arr) => (ele - arr[index-1]) === 1 || index === 0)

[Biwood]

好吧，没看到要找出缺少项，那就扩充一下

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]

@huang119412
@aureole999
@ipwx
不好意思各位，这个数组理论上是有序的，
业务场景可以想象成从数据库某表里取得的 id，id 对应所在行，先确认这一组 id 是否连续，不连续就找到缺失的数字

[kensoz]

@aureole999
这个数组可能不缺[1,2,3,4,5]
也可能缺 1 个[1,2,3,5]
也可能缺多个[1,2,5]
也可能在多个地方缺[3,5]

[chairuosen]

return arr.length - 1 === arr[arr.length-1] - arr[0]
O(1) 啊

[aureole999]

@kensoz 无重复的话可以先判断首尾相减+1 是否等于长度，等于的话就说明从数组开始的地方不缺，再判断一下第一个是不是 1，就不用往下走了。差 1 的话只缺一个，二分解决。差 2 以上的话数组再分一半，左右之间挨着的两个判断一下，然后左右递归，分别判断。速度最好 O(logn)，最差 O(n)。边界需要处理好。

[aureole999]

递归
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]

[...Array(arr[arr.length-1])].map((v, i) => (i+1)).filter((v,i)=>(!arr.includes(v)))

[wanguorui123]

[1,2,3,4,5,6].sort().every((v,i,arr)=>i>0?arr[i-1]+1==v:true)

[mxT52CRuqR6o5]

@kensoz 能保证从 1 开始吗？如果不能的话，如果缺的是两边的话是判断不出来的

[wanguorui123]

@wanguorui123 [1,2,3,4,5,6].every((v,i,arr)=>i>0?arr[i-1]+1==v:true)

[mxT52CRuqR6o5]

@kensoz
开头的数字不能确定，则无法判断出头部数字的缺失，尾部的数字如果不能确定，则无法判断出尾部数字的缺失

[kensoz]

@mxT52CRuqR6o5
用场景来举例就是一个表，记录一个东西并用 id 编号。
增加了 1，2，3id 后，删除了 2id，查询得目前剩下 1，3id，如果再有新增就用 2 来编号(最小的缺失数)
但是这个删除行为是随机的，不可控，所以理论上任何位数都有可能被删除
不过可以保证的是这一定是一个有序数组

ps:如果是后端直接用 sql 查询空位即可，但是数据交给前端处理的话，就相对麻烦了一下

[mxT52CRuqR6o5]

@kensoz
那我第一要考虑的就是“最小的缺失数”这个需求到底合不合理，最优先考虑是去否掉这个需求

[lrvinye]

@iMusic 中间的不管了？ 随手举个例子 [1,6,4,9,5]