程序员经验分享-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

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

  • 如何避免多系列折线图d3.js的工具提示重叠

    我已经在多系列折线图上创建了工具提示 如下所示在这里回答 https stackoverflow com questions 34886070 d3 js multiseries line chart with mouseover tool

  • 液体标记图过滤器示例

    我可以举一个有关 Liquid 贴图过滤器如何工作的通用示例吗 似乎没有这方面的文档 映射过滤器是 映射 收集给定属性上的数组 但如何确定该属性 这个例子存在 液体模板贴图过滤器 https stackoverflow com questi

  • （IE 特定）如何确定输入的文本是否比输入元素的宽度长

    这是所有版本 IE 特有的问题 在所有其他浏览器中 当文本溢出时 输入元素的scrollWidth 大于输入元素的clientWidth 有没有办法确定IE中输入字段中的文本超出了输入元素宽度的键 下面是一个检查 clientWidth 与

  • 优化重叠矩形的绘制

    我有很多矩形 有些与其他矩形重叠 每个矩形都有一个绝对 z 顺序和一个colour 每个 矩形 实际上是粒子效果 网格或纹理的轴对齐边界框 并且可能是半透明的 但只要您不尝试剔除其他矩形后面的矩形 就更容易抽象地思考彩色矩形 所以我将在问题

  • 在多个 angular.js 应用程序之间共享单个服务

    我正在构建一个电子商务网站 基于 shopify 并且使用多个小型 angularjs 应用程序来处理诸如快速购物车 愿望清单 过滤产品和其他一些较小项目之类的事情 我最初使用了一个大型应用程序 具有路由和所有内容 但当我没有完整的 RES

  • 如何验证单选按钮？

    我的 Rails 应用程序中有一个单选按钮 我想编写一个 java 脚本代码 在未选择任何选项时验证这一点 在你的 votes 类中做类似的事情 class Myvotes lt ActiveRecord Base validates vo

  • 压缩很多小字符串的算法？

    我正在寻找一种压缩小 ASCII 字符串的算法 它们包含大量字母 但也可以包含数字和很少的特殊字符 它们很小 平均约为 50 100 字节 最多 250 个字节 例子 Android show EditText setError above

  • 节省页面加载时间的提示[重复]

    这个问题在这里已经有答案了 我的问题 削减那些不必要的 kb 并使页面加载速度更快的最佳方法是什么 全部是什么优化实践 编码实践 在js php中 如果执行可以使您的页面更轻 为什么我问这个 我读了这篇关于 jquery js 与 jque

  • 无法将中间件与 Firebase 和 NuxtJS 3 一起使用

    我正在尝试在示例项目中使用 Firebase 身份验证 身份验证按预期工作 但是一旦我想使用中间件来阻止用户访问管理页面或在已经登录的情况下访问登录页面 这是不可能的 我已经尝试了几个小时 但没有任何效果 这是我的package json

  • 如何设置第三方 cookie

    我如何设置第三方 cookie 我有要求设置cookie 并且cookie将在访问的网站中启用 就像我在访问cde com或def com或ghi com时在abc com中设置cookie一样 所以设置的cookie将在所有网站上获取 我

  • Ajax调用完成后执行函数

    我是 Ajax 新手 我尝试在使用 for 循环时使用 Ajax Ajax 调用之后 我正在运行一个使用 Ajax 调用中创建的变量的函数 该函数只执行两次 我认为 Ajax 调用可能没有足够的时间在循环开始之前进行调用 有没有办法在运行

  • 用于计算有向图上非循环路径数量的快速算法

    简而言之 我需要一个fast计算简单有向图中有多少条非循环路径的算法 By simple我的意思是没有自环或多重边的图 Apath可以从任何节点开始 并且必须在没有传出边的节点上结束 一条路径是acyclic如果没有边出现两次 我的图 经验

  • 优化两个三位数乘积的最大回文数？

    我正在研究一个面试问题 我被问到这个问题 我应该编写一个程序 从两个三位数的乘积中找到最大的回文数 这里是question https projecteuler net problem 4 我想出了这种从底部开始的蛮力方法 public c

  • 添加元数据到快速路线

    有什么方法可以将元数据添加到 Express 的路线中吗 例如 app get some route function req res some meta data 我正在寻找一种针对我的节点应用程序的 AOP 方法 因此我想通过身份验证和

  • 多维数组将每个列表数组存储在另一个数组中

    我嵌套了可能有 2 或 3 层深度的多维数组 在它里面我可能有也可能没有列表数组 我需要循环数组 Array 0 gt Array id gt 1 name gt cat name 1 list gt Array 1 gt swgdgbdg

  • 检测浏览器是否支持 contentEditable？

    There s 这个问题 https stackoverflow com questions 3497942 browser detect contenteditable features 但发布的解决方案是浏览器嗅探 我试图避免这种情况

  • 为什么 C 函数不能返回数组类型？

    我是 C 语言新手 想知道 为什么 C 函数不能返回数组类型 我知道数组名是数组第一个值的地址 而数组是 C 中的二等公民 您自己已经回答了这个问题 数组是二等公民 C 按值返回 数组不能按值传递 因此不能返回它们 至于为什么数组不能按值传

  • 如何清除画布中图像上的矩形

    我需要清除画布中图像上绘制的矩形 而不损坏现有图像 我可以绘制小矩形点并将其清除 但问题是 当我清除矩形时 它在图像上仍保留为白色小斑点 有人可以告诉我如何清除图像上的矩形而不损坏现有图像 我使用了以下方法来清除矩形 但没有用 1 cont

  • 以特定顺序运行具有效果的 jQuery 函数

    我在 javascript 函数中有一些 jQuery 可以更改页面上的文本并以特定的时间间隔淡入和淡出 我希望这些函数在每个函数完成其效果后按顺序运行 dialogueExchange1 dialogueExchange2 dialogu

  • 使用 Google Visualization，为什么 DataView 内容显示在 ChartRangeFilter 中，而不显示在其关联的 LineChart 中？

    下面的代码应该从 CSV 文件填充 DataView 然后 DataView 被输入到 DashBoard 其中包含绑定在一起的 LineChart 和 ChartRangeFilter 我的问题是 虽然 ChartRangeFilter

随机推荐

热门标签