那些遇到过的问题

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

Ade*_*lin 28 javascript arrays algorithm

我有这个数组

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"];
Run Code Online (Sandbox Code Playgroud)

我试图找到一种能告诉我哪些s缺失的算法.正如你可以看到,该表包括连续的sS( ,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}`)
}
Run Code Online (Sandbox Code Playgroud)

但是这种方法失败了多个连续数字缺失(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}`)
    }
   }
}
Run Code Online (Sandbox Code Playgroud)

但是,我觉得我过于复杂了.我想创建一个理想的数组:

var idealArray = [];
for (var i =0; i<200;i++) {
  idealArray.push(i)
}
Run Code Online (Sandbox Code Playgroud)

然后,在检查时,篡改我的数组(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")
  }
}
Run Code Online (Sandbox Code Playgroud)

但是,再一次,我觉得创建第二个阵列也不是很有效(考虑一个大的列表,我会浪费不必要的空间).

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

Mar*_*yer 15

既然你知道你期望一个顺序数组,我不知道为什么它需要比循环数字更复杂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]}` )
}
Run Code Online (Sandbox Code Playgroud)

编辑:

在仔细考虑下面的评论后,我做了一个递归方法,分割数组并检查每一半.主要是作为一个实验,而不是一个实际的解决方案.事实上,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]]}`))
Run Code Online (Sandbox Code Playgroud)

也许另一个答案或评论会有一个改进,使它更快一点.

  • `这将在O(n)运行,但我认为你不能改进它.正如我在评论中提到的,你应该能够将它降低到O(log n).您只能对阵列的小部分进行线性扫描,并对大型部分进行二进制切割,丢弃任何没有丢失数字的部分.例如,如果你缩小到`["s00","s01","s02","s03"],你就会知道没有任何遗漏,因为第一个元素是"0",最后一个是"3".长度为"4" - 这意味着没有任何遗漏.不可否认,它的实施工作更多,但对于大型阵列来说速度更快. (10认同)
  • 对于@ vlaz的算法,根据阵列的大小(N)和要识别的缺失元素的数量(M)来测量复杂度更准确.需要打印每个缺少的元素,并且可以在O(log N)中找到每个缺少的元素.所以最坏的情况是O(M log N).但是,在非常稀疏的数组中,缺失的元素将会跨越; 在这种情况下,可以在O(log N)中找到整个跨度.如果S是跨距数,则复杂度为O(M + S log N).由于S <= N + 1,最坏的情况是O(M + N log N).(O(M)是打印缺失的元素.)此外,S <= M,fwiw. (3认同)
  • 刚刚在飞机上编写了这个解决方案,并准备在登陆时发布:)(无论如何我在你添加它之前投了票) (2认同)

Ves*_*dov 6

据我理解的理想阵列解决方案,您知道最大阵列大小(？).因此,如果您有100个最大值并且期望S00-S99,您可以:

var arrayIndex=0;
for (var i =0; i<100;i++) {
   var idealValue="s"+("00"+i).slice(-2); // To get S01-S99
   if(arr.length <= arrayIndex || arr[arrayIndex]!=idealValue){
        console.log(idealValue + 'is missing');
   }
   arrayIndex++;
}
Run Code Online (Sandbox Code Playgroud)

或类似的东西.我现在无法测试它;)但是迭代理想值列表并比较数组中的相同值.如果不匹配则打印出来.

And*_*kin 5

您与内部溶液while-loop似乎已经相当不错了,只是省略不必要的if,并跟踪您当前希望看到的,而不是每次都解析对上号的数量.

像这样的东西:

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"];
var expectedI = 0
for (var i = 0; i < arr.length; i++) {
  var currentI = parseInt(arr[i].toLowerCase().split("s")[1]);
  while (expectedI < currentI) {
    console.log(`Seems like ${expectedI} is missing.`)
    expectedI++
  }
  expectedI = currentI + 1
}
Run Code Online (Sandbox Code Playgroud)

给你:

Seems like 6 is missing.
Seems like 15 is missing.
Seems like 16 is missing.
Seems like 18 is missing.
Seems like 23 is missing.
Seems like 29 is missing.
Seems like 31 is missing.
Seems like 35 is missing.
Seems like 37 is missing.
Seems like 40 is missing.
Seems like 42 is missing.
Seems like 57 is missing.
Seems like 59 is missing.
Seems like 66 is missing.
Seems like 68 is missing.
Run Code Online (Sandbox Code Playgroud)

这个想法非常简单:如果您没有看到预期看到的数字,请将其打印到控制台(或将其保存在其他位置),然后继续下一个数字.

请注意,您无法获得下面的运行时O(N),因为您必须至少查看一次列表中的每个元素,并且还可能需要将O(N)缺少的元素打印到控制台.

上面的算法一次查看列表的每个元素,并且可以在恒定的空间开销下运行.

编辑:该由vlaz作出评论似乎提出了一个算法,应该运行速度更快几乎没有缝隙阵列.但是,这仍然不会改变最坏情况的行为,因为在最坏的情况下(如果一切都缺失),您仍然需要打印所有N数字.如果您假设k缺失数字的数量"远小于" N(即k不存在Theta(N)),则可以实现更高效的算法.

归档时间：

查看次数：

2584 次

最近记录：

7 年，3 月 前
相关归档
立即函数调用语法 110
如何保存Backbone.js模型数据？ 86
setState不会立即更新状态 72
本地存储与AngularJS $ cacheFactory 58
向上/向下舍入到最近的分钟 51
使用Redux获取数据时如何避免竞争条件？ 44
关于JavaScript的切片和拼接方法的问题 23
Numpy Indexing:返回其余部分 19
将整数转换为字符数组:java 16
访谈:关于人员匹配 9
难疑归档
检查shell脚本中是否存在目录 3556
如何在JavaScript中获取查询字符串值？ 2701
如何从YouTube API获取YouTube视频缩略图？ 2291
什么是Android上的"上下文"？ 1872
如何按字典值对字典列表进行排序？ 1722
重命名pandas中的列 1601
在Vim中复制整行 1555
为什么将0.1f改为0会使性能降低10倍？ 1491
const和readonly有什么区别？ 1269
抵消html锚点以调整固定标题 1056