程序员经验分享-hwhale

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

2024-04-10

我有这个数组

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"];

我试图找到一种算法来告诉我哪个ss 失踪了。如您所见，该列表由连续的ss (s1, s2, etc.).

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

    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)。）


既然您知道您正在期待一个顺序数组，我不知道为什么它需要比数字循环更复杂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]}` )
}

EDIT:

After thinking a bit about the comments below, I made a recursive approach that splits the array and checks each half. Mostly as an experiment, not as a practical solution. This does in fact run with fewer than n iterations in most cases, but I couldn't find a case where it was actually faster Also, I just pushed indexes showing where the gaps are to make the structure easier to see and test. And as you'll see, because it's recursive the results aren't in order.

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]]}`))

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

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

javascript

Arrays

Algorithm

如何有效检查连续数字列表是否缺少任何元素 的相关文章

  • 网络上的等角柱状图

    我计划为游戏的标记 图钉 构建在线地图 但我无法设置标记的正确纬度 原始地图是一个2048 2048px 的正方形 然后我得到了标记 数千个 地图坐标使用 0 到 100 之间的 x y 表示法设置 0 0 是top left角和100 1

  • querySelector 搜索直接子级[重复]

    这个问题在这里已经有答案了 我有一些类似 jquery 的函数 function elem return gt someselector elem 问题是我怎样才能做同样的事情querySelector 问题是 gt 选择器中querySe

  • 玉石压痕错误

    因此 对于我的 Express 网站 我使用 jade 所以我决定尝试修改我的布局文件 以便我可以开始设计我的网站 我修改了原始布局代码 有效 但我开始在任何扩展布局的文件中出现缩进错误 如下所示 500 Error home kevin

  • 鼠标移动时画布拖动

    我正在尝试构建一个可以使用鼠标移动拖动的画布 我做了一些我无法理解的错误 因为一开始似乎有效 然后出现了一个增量错误 使画布移动得太快 考虑以下代码 window onload function var canvas document ge

  • 使用 babel env 预设时，展开运算符出现语法错误

    我正在努力 现代化 meern io 入门样板 https github com Hashnode mern starter通过替换巴别塔es2015 and stage 0预设为env 然而 似乎env预设无法识别以下片段client m

  • 动态规划的复杂组合条件

    我正在探索动态规划设计方法如何与问题的底层组合属性相关 为此 我正在查看的规范实例硬币找零问题 Let S d 1 d 2 d m and n gt 0是请求的金额 我们可以用多少种方式相加n仅使用中的元素S 如果我们遵循一个动态规划如果要

  • 从 puppeteer PDF 中删除分页符？

    我目前正在尝试查看是否有一种方法可以删除我的 puppeteer PDF 中的分页符 因为我当前的 PDF 设置中的一些分页符正在以一种奇怪的方式切断文本 我正在谈论的内容的屏幕截图 我的傀儡代码 app get companyId pdf

  • 解释一下这个令人困惑的 dojo 教程声明语法

    我正在阅读使用的语法道场的声明 http dojotoolkit org documentation tutorials 1 8 declare 用于班级创建 描述很混乱 The declare function is defined in

  • 将所有奇数位置的元素移动到左半部分，将偶数位置的元素移动到右半部分

    给定一个包含正整数和负整数的数组 将所有奇数索引元素移动到左侧 将偶数索引元素移动到右侧 问题的难点是在维持秩序的同时就地做 e g 7 5 6 3 8 4 2 1 输出应该是 5 3 4 1 7 6 8 2 如果顺序不重要 我们可以使用快

  • 指定 HTML5 输入类型 = 日期的值输出？

    我想将本机日期选择器添加到我的应用程序中 该应用程序当前使用遗留的本地系统 日期输入支持尚未广泛普及 但如果我可以基于兼容性提供这两种实现 那就太理想了 有没有办法指定 HTML 日期选择器给出的值的输出 歌剧的默认设置是yyyy mm d

  • 插件 gulp-babel 错误：插件/预设文件不允许导出对象，只能导出函数

    我现在尝试在我的 Ionic v1 应用程序中使用 JavaScript 2015 ES6 包 json name test version 1 0 0 dependencies ionic native deeplinks 4 18 0

  • 替换img路径jquery

    我正在尝试替换 jquery 中的 img 路径 注入远程页面 replaceexample com thumbs withexample com images 我已经尝试过这个 但似乎不起作用 img attr src replace t

  • NodeJS - 将相对路径转换为绝对路径

    In my 文件系统我的工作目录在这里 C temp a b c d 在 b bb 下有文件 tmp txt C temp a b bb tmp txt 如果我想从工作目录转到该文件 我将使用以下路径 bb tmp txt 如果该文件不存在

  • 将默认搜索文本添加到搜索框 html

    我正在努力将 搜索 文本添加到搜索框 我正在努力实现 onfocus 消失文本 And onblur 重新出现文本 到目前为止 我已经实现了这一点 但我必须将其硬编码为 html eg

  • 当rest api应用程序服务器（express）和Angulars js应用程序在不同端口上运行时出现Cors问题

    我有用node js编写的rest api应用程序 express在端口3000上运行 而angularjs应用程序在同一服务器上的端口9001上运行 从 angularjs 应用程序调用 rst api 时 出现了 cors 问题 在re

  • 从浏览器访问本地文件？

    您好 我想从浏览器访问系统的本地文件 由于涉及大量安全检查 是否可以通过某种方式实现这一目标 或使用 ActiveX 或 Java Applet 的任何其他工作环境 请帮帮我 要通过浏览器访问本地文件 您可以使用签名的 Java Apple

  • WebpackError：ReferenceError：Gatsby 上未定义窗口

    我已经在互联网上进行了大量搜索 但无法解决这个问题 我正在使用 Gasby 开发静态页面 但遇到此错误 WebpackError ReferenceError window is not defined 我的线索是 这与我正在使用的引导 模

  • jQuery UI 对话框 - 关闭后无法打开

    我有一个问题jquery ui dialog box https jqueryui com dialog 问题是 当我关闭对话框然后单击触发它的链接时 除非刷新页面 否则它不会再次弹出 如何在不刷新实际页面的情况下回调对话框 下面是我的代码

  • YouTube 点击时禁用 HTML5

    有没有办法让我们通过javascript禁用HTML5视频的 播放 暂停 点击全屏 功能 然后在我们再次需要时将其放回去 我不知道你是否可以禁用它们 但你可以使用 css 删除它们 video webkit media controls f

  • jQuery appendTo(), json 在 IE 6,7,8 中不起作用

    我这两天绞尽脑汁想找到解决办法 我使用 jQuery ajax 从数据库中获取值 以便在另一个框发生更改时更新一个框 php 脚本从数据库中获取值 然后输出 json 它在 FF 中工作正常 但在所有版本的 IE 中 选择框都不会更新 我已

随机推荐

热门标签