javascript - 如何有效地检查连续数字列表是否缺少任何元素

Question

我有这个数组

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

我试图找到一种算法来告诉我缺少哪些 s。如您所见，该列表由连续的 s(s1、s2 等)组成。

起初我采用了这个解决方案:

    var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
for (var i=1;i<arr.length;i++){
    var thisI = parseInt(arr[i].toLowerCase().split("s")[1]);
    var prevI = parseInt(arr[i-1].toLowerCase().split("s")[1]);
    if (thisI != prevI+1)
      console.log(`Seems like ${prevI+1} is missing. thisI is ${thisI} and prevI is ${prevI}`)
}

但是如果缺少一个以上的连续数字(s15、s16)，此方法将失败。所以我添加了一个有效的 while 循环。

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
for (var i=1;i<arr.length;i++){
  var thisI = parseInt(arr[i].toLowerCase().split("s")[1]);
  var prevI = parseInt(arr[i-1].toLowerCase().split("s")[1]);
  if (thisI != prevI+1) {
    while(thisI-1 !== prevI++){
       console.log(`Seems like ${prevI} is missing. thisI is ${thisI} and prevI is ${prevI}`)
    }
   }
}

但是，我觉得我把事情复杂化了。 我想创建一个理想的数组:

var idealArray = [];
for (var i =0; i<200;i++) {
  idealArray.push(i)
}

然后，在检查时篡改我的数组 (arr)，以便循环检查两个长度相同的数组。即，使用此解决方案:

var idealArray = [];
for (var i =0; i<200;i++) {
  idealArray.push(i)
}
var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
for (let i = 0; i<idealArray.length;i++){
  if (parseInt(arr[i].toLowerCase().split("s")[1]) != idealArray[i]) {
    console.log(`Seems like ${idealArray[i]}is missing`);
    arr.splice(i,0,"dummyel")
  }
}

但是，再一次，我觉得创建第二个数组的效率也不是很高(考虑到一个大列表，我会浪费不必要的空间)。

那么...我如何在 JavaScript 中高效地执行此任务？ (高效意味着时间复杂度和空间复杂度都尽可能接近 O(1)。)

Answer 1

既然你知道你需要一个顺序数组，我不知道为什么它需要比通过数字 arr[0] 到 arr[end]< 的循环更复杂 同时保留一个计数器以了解您在数组中的位置。这将以 O(n) 的速度运行，但我认为您无法对此进行改进 — 在最坏的情况下，您需要至少查看每个元素一次。

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let first = parseInt(arr[0].substring(1))
let last =  parseInt(arr[arr.length-1].substring(1))
let count = 0
for (let i = first; i< last; i++) {
   if (parseInt(arr[count].substring(1)) == i) {count++; continue}
   else console.log(`seem to be missing ${'s'+i.toString().padStart(2,'0')} between: ${arr[count-1]} and ${arr[count]}` )
}

---

编辑:

在仔细考虑下面的评论之后，我采用了一种递归方法来拆分数组并检查每一半。主要作为实验，而不是实际解决方案。在大多数情况下，这确实以少于 n 的迭代次数运行，但我找不到它实际上更快的情况另外，我只是推送了显示差距的索引以使结构更容易查看和测试。 正如您将看到的，因为它是递归的，所以结果不是按顺序排列的。

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let missingGaps = []

function missing(arr, low, high) {
  if (high <= low) return

  let l = parseInt(arr[low].substring(1))
  let h = parseInt(arr[high].substring(1))

  if (h - l == high - low) return
  if (high - low === 1) {
    missingGaps.push([low, high])
    return
  } else {
    let mid = ((high - low) >> 1) + low
    
    missing(arr, low, mid)

    // need to check case where split might contain gap
    let m = parseInt(arr[mid].substring(1))
    let m1 = parseInt(arr[mid + 1].substring(1))
    if (m1 - m !== 1) missingGaps.push([mid, mid + 1])

    missing(arr, mid + 1, high)
  }
}

missing(arr, 0, arr.length-1)
missingGaps.forEach(g => console.log(`missing between indices ${arr[g[0]]} and ${arr[g[1]]}`))

也许另一个答案或评论会有所改进，使其更快一些。