javascript - saber - faltantes en una lista de números consecutivos sql server
Cómo verificar de manera eficiente si a una lista de números consecutivos le falta algún elemento (12)
Aquí está el enfoque recursivo basado en la respuesta aceptada pero refactorizado para devolver los datos:
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"];
function findMissing(arr, l, r) {
var lval = Number(arr[l].substr(1));
var rval = Number(arr[r].substr(1));
// the segment has no gaps
if (r - l === rval - lval) {
return [];
}
// the segment has exactly two items
if (r - l === 1) {
return Array.from({ length: rval - lval - 1 }, function(x, i) {
return "s" + (lval + 1 + i);
});
}
// calculate middle using integer cast trick
var m = (l + r) / 2 | 0;
// process the segments [l, m] and [m, r]
// note that m is processed twice and requires extra recursion
// however this eliminates the extra coding needed to handle
// the case where m and m + 1 are not consecutive
return findMissing(arr, l, m).concat(findMissing(arr, m, r));
}
var result = findMissing(arr, 0, arr.length - 1);
console.log(result);
Tengo esta matriz
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"];
Estaba tratando de encontrar un algoritmo que me dijera cuáles faltan. Como puede ver, la lista consta de s s consecutivos ( s1 , s2 , etc.).
Al principio fui con esta solució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"];
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}`)
}
Pero este método falla por más de una falta de números consecutivos ( s15 , s16 ). Así que agregué un bucle while que funciona.
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}`)
}
}
}
Sin embargo, siento que estoy complicando demasiado las cosas. Pensé en crear una matriz ideal:
var idealArray = [];
for (var i =0; i<200;i++) {
idealArray.push(i)
}
Y luego, mientras verifica, manipula mi matriz ( arr ) para que el bucle verifique dos matrices de la misma longitud. Es decir, usa esta solución:
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")
}
}
Pero, una vez más, tengo la sensación de que crear esta segunda matriz tampoco es muy eficiente (pensando en una gran lista, perdería espacio innecesario).
Entonces ... ¿cómo realizo esta tarea de manera eficiente en JavaScript? (Significa eficientemente lo más cerca posible de O (1) tanto para la complejidad del tiempo como para la complejidad del espacio.)
Como entiendo por su solución de matriz ideal, usted sabe el tamaño máximo de matriz (?). Entonces, si tiene 100 valores máximos y espera S00 - S99, puede hacer:
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++;
}
O algo así. No puedo probarlo ahora;) Pero repita la lista de valores ideales y compare el mismo valor en la matriz. Si no coincide, imprímelo.
Como sabe que está esperando una matriz secuencial, no sé por qué debe ser más complicado que un bucle a través de los números arr[0] a arr[end] mientras mantiene un contador para saber dónde se encuentra en la matriz. Esto se ejecutará en O (n), pero no creo que puedas mejorar eso, debes mirar cada elemento al menos una vez en el peor de los casos.
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:
Después de pensar un poco en los comentarios a continuación, hice un enfoque recursivo que divide la matriz y verifica cada mitad. Principalmente como un experimento, no como una solución práctica. De hecho, esto se ejecuta con menos de n iteraciones en la mayoría de los casos, pero no pude encontrar un caso en el que fuera realmente más rápido. Además, solo presioné los índices que muestran dónde están las brechas para que la estructura sea más fácil de ver y probar. Y como verás, porque es recursivo los resultados no están en orden.
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]]}`))
Tal vez otra respuesta o comentario tenga una mejora que lo haga un poco más rápido.
Entonces, si sabe que no hay duplicados y que las entradas están en orden, un proceso bastante simple sería comenzar por verificar el número de elementos en la lista.
La longitud de arr debe ser igual al número de elementos consecutivos, ¿sí?
*** Advertencia: si los elementos no están ordenados o podría haber duplicados, esto no funcionará, por supuesto.
Asumiendo que las condiciones se aplican, entonces una simple búsqueda binaria encontraría el primer elemento faltante.
Después de eso, es una división y conquista, con la búsqueda binaria limitada a la parte superior del espacio de búsqueda para encontrar el siguiente elemento faltante. Un algoritmo recursivo sería fácil de entender, pero también podría hacerlo en una sola función.
Tenga en cuenta que los elementos contienen una relación entre sus índices de lista. En su búsqueda binaria, si "s08" está en el elemento siete, entonces sabe que falta un elemento anteriormente en la matriz.
La búsqueda binaria es bastante fácil, y probablemente también se beneficiaría de una forma de comparación menos ingenua, ya que los elementos son una cadena de campo fija.
El ajuste de los elementos faltantes también es bastante fácil. Cada elemento faltante desplaza el resto de los elementos un índice a la izquierda, de modo que se convierte en una operación de entero simple.
¿Seriamente? No es tan difícil:
#include <stdio.h>
#include <stdlib.h>
#define ARY_SZ 68
static
int arr[ARY_SZ] =
{
1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 45, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 70
};
int
main(
void )
{
int i,
lim,
lo,
hi,
mid,
val,
cnt;
/* Pre-check. */
lim = arr[ARY_SZ - 1] - (ARY_SZ - 1);
if (lim == 0)
{
/* No missing elements. */
printf(
"No missing elements./n" );
return 0;
}
/* Initialize binary search. */
lo = 0;
hi = ARY_SZ;
cnt = 0;
/* For (at most) the number of array elements, do: */
for (i = 0; i < ARY_SZ && cnt < lim; i++)
{
/* Get mid point of search. */
mid = lo + hi >> 1;
/* Get array value, adjust and do comparisons. */
val = arr[ mid ] - cnt;
if (val == mid)
lo = mid + 1;
if (val > mid)
hi = mid - 1;
if (lo > hi)
{
/* Report missing element. */
printf(
"Missing element @ arr[ %d ] == %d, probes = %d/n",
lo,
arr[ lo ],
i );
/* Divide and conquer. */
hi = ARY_SZ;
cnt += 1;
}
}
printf(
"Probes = %d/n",
i - 1);
return 0;
}
Los resultados de compilar este código C y ejecutarlo:
Missing element @ arr[ 0 ] == 1, probes = 5
Missing element @ arr[ 43 ] == 45, probes = 11
Missing element @ arr[ 67 ] == 70, probes = 16
Probes = 16
Por lo tanto, no se necesita una búsqueda lineal, y se requiere un máximo de 16 sondas para encontrar los tres elementos que faltan.
Esta versión llena una matriz con todos los valores posibles y luego selecciona los que faltan:
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 fullArray = Array(71).fill().map((item, index) => "s"+(""+(0 + index)).padStart(2,"0"));
var missingValues = fullArray.filter( ( el ) => !arr.includes( el ) );
console.log(missingValues);
Con un poco más de legibilidad y reutilizació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"];
var prependString = "s";
var numberOfDigits = 2;
var initialNumber = 0;
var finalNumber = 70;
var fullArray = Array(finalNumber - initialNumber + 1)
.fill()
.map((item, index) => prependString+(""+(initialNumber + index)).padStart(numberOfDigits,"0"));
var missingValues = fullArray.filter( ( el ) => !arr.includes( el ) );
console.log(missingValues);
Este es solo un método para encontrar si, en una matriz dada, falta algún elemento en una secuencia numérica. Podríamos usar (n * (n + 1)) / 2 que resuelve la suma en n primeros números. Además, si la matriz comienza con, por ejemplo, 10, eliminamos 1-10 sum. Esto solo nos dice si falta algo, pero no lo que falta. La ventaja es que la matriz podría ser sin clasificar. Calcular mínimo es menos costoso que ordenar toda la matriz.
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");
Podría reducir la matriz tomando dos elementos de la matriz y rellenar los huecos, si existen.
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);
Puede optar por algo como esto que compare cada elemento de la matriz con el que está al lado, luego, si la diferencia es mayor que 1, se pueden registrar todos los números intermedios.
const 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 < arr.length - 1; i++) {
let currentNum = parseInt(arr[i].split("s")[1]);
let difference = parseInt(arr[i + 1].split("s")[1]) - currentNum;
if (difference === 1) continue
for (let d = 1; d < difference; d++)
console.log(`Seems likes ${currentNum+d} is missing`)
}
Espero que encuentres esto útil.
Su solución con el interior while -loop ya parece bastante buena, simplemente omita el innecesario if , y realice un seguimiento del número que actualmente espera ver en lugar de analizar el número anterior cada vez.
Algo como esto:
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
}
te dio:
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.
La idea es muy simple: si no ve el número que esperaba ver, imprímalo en la consola (o guárdelo en otro lugar), luego continúe con el siguiente número.
Tenga en cuenta que no puede obtener el tiempo de ejecución por debajo de O(N) , porque tiene que mirar todos los elementos de la lista al menos una vez, y también podría suceder que tenga que imprimir elementos faltantes de O(N) en la consola.
El algoritmo anterior examina cada elemento de la lista una vez y puede funcionar con una sobrecarga de espacio constante.
EDITAR: El comentario hecho por vlaz parece proponer un algoritmo que debería funcionar más rápido para arreglos con pocos huecos. Sin embargo, esto todavía no cambia el comportamiento del peor de los casos, porque en el peor de los casos (si falta todo), todavía tiene que imprimir todos los números N Si asume que el número k de números faltantes es "mucho más pequeño" que N (es decir, k no está en Theta(N) ), podrían ser posibles algoritmos más eficientes.
Una solución rápida y sencilla es unir todos los elementos de una matriz en una cadena y luego buscar dentro de esa cadena.
Aquí hay una solución que toma una matriz (ordenada o no ordenada, funciona bien en cualquier caso) con cualquier patrón (no se necesita un patrón s0x codificado):
const 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 firstIndex = Number(arr[0].replace(//D/, ''''));
let lastIndex = Number(arr[arr.length-1].replace(//D/, ''''));
let separator = '','';
let arrString = separator + arr.join(separator) + separator;
for (let i = firstIndex; i <= lastIndex; i++) {
let element = arr[0].slice(0, arr[0].length - String(i).length) + i;
if (arrString.indexOf(separator + element + separator) < 0) {
console.log(element)
}
}
Usando una variedad de booleanos para realizar un seguimiento de los elementos presentes:
let numbers = arr.map(s => +s.slice(1)); // Convert to numbers
let maximum = Math.max.apply(null, numbers); // Get the maximum
let missing = Array(maximum).fill(true); // start with all missing
let answer = numbers.reduce((p, c) => (p[c] = false, p), missing); // set to false if there
answer.forEach((e,i) => (e && console.log(i + " seems to be missing"))); // show answer
También funciona para números dispuestos al azar.
Versión de Javascript del programa C anterior, uno que permite secuencias de elementos faltantes.
var util = require( ''util'' );
// Array of data.
var arr = [
1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 46, 47, 48, 49,
50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
60, 61, 62, 63, 64, 65, 66, 67, 68, 70
];
var arr_len = arr.length;
// Empty array?
if (arr_len == 0)
{
console.log(
util.format(
"No elements." ));
process.exit( 0 );
}
// Pre-check.
var lim = arr[arr_len - 1] - (arr_len - 1);
if (lim == 0)
{
printf(
"No missing elements./n" );
return 0;
}
// Initialize binary search.
var lo = 0;
var hi = arr_len;
var mid = 0;
// Search metadata.
var cnt = 0;
var prv = 0;
var val = 0;
var i;
for (i = 0; i < arr_len && cnt < lim; i++)
{
// Get mid point of search.
mid = (lo + hi) >> 1;
// Get array value, adjust and do comparisons
val = arr[ mid ] - cnt;
if (val === mid)
lo = mid + 1;
if (val > mid)
hi = mid - 1;
// Have we found something?
if (lo > hi)
{
// Yes. Divide and conquer.
hi = arr_len;
prv = cnt;
cnt = arr[ lo ] - lo;
// Report missing element(s).
console.log(
util.format(
"Missing %d elements @ arr[ %d ] == %d, probes = %d",
cnt - prv,
lo,
arr[ lo ],
i + 1 ));
}
}
console.log(
util.format(
"Probes: %d",
i ));