如何有效地检查连续数字列表是否缺少任何元素 [英] How to efficiently check if a list of consecutive numbers is missing any elements
问题描述
我有这个数组
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缺失。如您所见，该列表包含连续的 s s（ s1 ， s2 等。）。
I was trying to find an algorithm that will tell me which ss are missing. As you can see, the list consists of consecutive ss (s1, s2, etc.).
起初我选择了这个解决方案：
At first I went with this solution:
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 ）。所以我添加了，而循环有效。
But this method fails for more than one consecutive numbers missing (s15, s16). So I added a while loop which works.
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}`)
}
}
}
然而，我觉得我过于复杂的东西。
我想创建一个理想的数组：
However, I feel like I'm overly complicating things. I thought of creating an ideal array:
var idealArray = [];
for (var i =0; i<200;i++) {
idealArray.push(i)
}
然后，在检查时，篡改我的数组（ arr ），以便循环检查两个长度相同的数组。即，使用此解决方案：
And then, while checking, tamper with my array (arr) so that the loop checks two arrays of the same length. I.e., use this solution:
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")
}
}
但是，再一次，我觉得创建第二个阵列也不是很有效（考虑一个大的列表，我会浪费不必要的空间）。
But, once again, I have the feeling that creating this second array is not very efficient either (thinking of a big list, I'd waste unnecessary space).
那么......我如何在JavaScript中有效地执行此任务？ （有效地表示时间复杂度和空间复杂度都尽可能接近O（1）。）
So... how do I efficiently perform this task in JavaScript? (Efficiently meaning as close to O(1) as possible both for time complexity and for space complexity.)
推荐答案
因为你知道你期待一个顺序数组，我不知道为什么它需要比循环数字更复杂 arr [0] 通过 arr [结束] 同时保持计数器知道你在阵列中的位置。这将在O（n）运行，但我不认为你可以改进 - 你需要在最坏的情况下至少查看一次每个元素。
Since you know you are expecting a sequential array, I don't know why it needs to be more complicated than a loop through numbers arr[0] through arr[end] while keeping a counter to know where you are in the array. This will run at O(n), but I don't think you can improve on that — you need to look at every element at least once in the worst case.
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 ，但是我找不到实际上更快的情况。另外，我只是推动索引显示差距在哪里是为了使结构更容易看到和测试。 正如你所看到的，因为它是递归的，所以结果不合理。
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]]}`))
也许另一个答案或评论会有一个改进，使其更快一点。
Maybe another answer or comment will have an improvement that makes it a bit faster.
这篇关于如何有效地检查连续数字列表是否缺少任何元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
