Comment vérifier efficacement s'il manque des éléments dans une liste de nombres consécutifs ?

Question

J'ai ce tableau

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

J'ai essayé de trouver un algorithme qui me dira quelle s sont absents. Comme vous pouvez le voir, la liste se compose de consécutifs s s ( s1 , s2 etc.).

Au début, j'ai opté pour cette 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}`)
}

Mais cette méthode échoue pour plus d'un numéro consécutif manquant ( s15 , s16 ). J'ai donc ajouté un while boucle qui fonctionne.

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

Cependant, j'ai l'impression de compliquer excessivement les choses. J'ai pensé à créer un tableau idéal :

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

Et ensuite, pendant la vérification, trafiquer mon tableau ( arr ) afin que la boucle vérifie deux tableaux de même longueur. Autrement dit, utilisez cette 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")
  }
}

Mais, encore une fois, j'ai l'impression que la création de ce deuxième tableau n'est pas non plus très efficace (en pensant à une grande liste, je gaspillerais de l'espace inutile).

Alors... comment puis-je réaliser efficacement cette tâche en JavaScript ? (Efficace signifie aussi proche de O(1) que possible à la fois pour la complexité temporelle et pour la complexité spatiale).

Answer 1

Puisque vous savez que vous attendez un tableau séquentiel, je ne vois pas pourquoi cela devrait être plus compliqué qu'une boucle à travers des nombres. arr[0] par le biais de arr[end] tout en gardant un compteur pour savoir où vous êtes dans le tableau. Cela fonctionnera à O(n), mais je ne pense pas que vous puissiez améliorer cela - vous devez regarder chaque élément au moins une fois dans le pire des cas.

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

---

EDITAR:

Après avoir réfléchi un peu aux commentaires ci-dessous, j'ai fait une approche récursive qui divise le tableau et vérifie chaque moitié. C'est surtout une expérience, pas une solution pratique. En fait, cela fonctionne avec moins de n itérations dans la plupart des cas, mais je n'ai pas pu trouver un cas où il était réellement plus rapide Aussi, j'ai juste poussé des index montrant où sont les lacunes pour rendre la structure plus facile à voir et à tester. Et comme vous le verrez, comme c'est récursif, les résultats ne sont pas dans l'ordre.

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

Peut-être qu'une autre réponse ou un autre commentaire apportera une amélioration qui le rendra un peu plus rapide.

Answer 2

Si je comprends bien votre solution de tableau idéal, vous connaissez la taille maximale du tableau ( ?). Donc si vous avez 100 valeurs maximales et que vous attendez S00 - S99, vous pouvez le faire :

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++;
}

Ou quelque chose comme ça. Je ne peux pas le tester pour l'instant ;) Mais itérer à travers la liste des valeurs idéales et comparer la même valeur dans le tableau. Si elle ne correspond pas, imprimez-la.

Answer 3

Votre solution avec l'intérieur while -La boucle semble déjà très bien fonctionner, il suffit d'omettre les éléments inutiles. if et de garder la trace du nombre que vous attendez actuellement au lieu d'analyser le nombre précédent à chaque fois.

Quelque chose comme ça :

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
}

vous donne :

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.

L'idée est très simple : si vous ne voyez pas le nombre que vous vous attendiez à voir, imprimez-le sur la console (ou enregistrez-le ailleurs), puis continuez avec le nombre suivant.

Notez que vous ne pouvez pas obtenir le temps d'exécution ci-dessous O(N) parce qu'il faut regarder chaque élément de la liste au moins une fois, et il peut aussi arriver que l'on doive imprimer O(N) les éléments manquants à la console.

L'algorithme ci-dessus examine chaque élément de la liste une fois, et peut fonctionner avec un encombrement constant.

EDITAR: Le site commentaire fait par vlaz semble proposer un algorithme qui devrait fonctionner plus rapidement pour les tableaux avec peu de trous. Cependant, cela ne change toujours pas le comportement dans le pire des cas, car dans le pire des cas (si tout est manquant), vous devez toujours imprimer tous les tableaux N nombres. Si vous supposez que le nombre k de numéros manquants est "beaucoup plus faible" que N (c'est-à-dire k pas dans Theta(N) ), des algorithmes plus efficaces pourraient être envisagés.

Answer 4

Vous pouvez réduire le tableau en prenant deux éléments du tableau et remplir les vides, s'ils existent.

const
    getNumber = s => +s.slice(1),
    pad = i => ('00' + i).slice(-2);

var array = ["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"],
    result = [];

array.reduce((left, right) => {
    var l = getNumber(left),
        r = getNumber(right);

    while (++l < r) {
        result.push('s' + pad(l));
    }
    return right;
});

console.log(result);

Answer 5

Il s'agit simplement d'une approche permettant de déterminer si, dans un tableau donné, il manque un élément dans une séquence de chiffres. Nous pourrions utiliser (n*(n+1))/2 qui résout l'addition sur les n premiers nombres. De même, si le tableau commence par exemple par 10, nous supprimons la somme 1-10. Cela nous indique simplement si quelque chose manque, mais pas ce qui manque. L'avantage est que le tableau peut être non trié. Calculer le minimum est moins coûteux que de commander le tableau entier.

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 total = 0;

for(let i = 0; i<arr.length; i++){
    arr[i] = parseInt(arr[i].replace("s", ""));
    total += arr[i];
}

let hipFirstSum = ((arr[0]-1)*(arr[0]))/2;  //or minimun
let n = arr[arr.length -1];
let hipSum = (n*(n+1))/2;
let realSum = hipSum - hipFirstSum;

(realSum != total)?console.log("wrong"):console.log("good");