Dada una lista de números con solo 3 números únicos (1, 2, 3), clasifique la lista en O (n) tiempo. Además, clasifique la matriz con espacio constante O (1) .
Ejemplo:
Input: [3, 3, 2, 1, 3, 2, 1]
Output: [1, 1, 2, 2, 3, 3, 3]
Aquí la solución que hice (no es un espacio O (1) y tiene espacios vacíos en la matriz ...): lo que hace esta función es simple ... aumenta el tamaño de la disposición al doble en el caso de que todos sus elementos sean 2 ; Luego pasa a su longitud anterior (actual / 2) para ordenar sus elementos ... si es 1 no hace nada, si encuentra un 2 lo coloca en la longitud máxima anterior + 1, aumenta la variable len y elimina el elemento y si es 3 empuje y elimine el elemento ... entonces tiene espacios vacíos en la matriz y no encuentra el punto positivo del problema, pero es O (n).
function sort(list) {
let len = list.length;
list.length=len*2
for(let i=0; i<list.length/2; i++){
let n=list[i]
if(n==2){
list[len]=n
delete list[i]
len++
}else if(n==3){
list.push(n)
delete list[i]
}
}
return list
}
console.log(sort([1,2,3,2,1,1]))4 respuestas
Puede usar el algoritmo del Problema de la bandera nacional holandesa:
El problema de la bandera nacional holandesa 1 es un problema de programación informática propuesto por Edsger Dijkstra (en un capítulo de su libro Una disciplina de programación Prentice-Hall, 1976). La bandera de los Países Bajos consta de tres colores: rojo, blanco y azul. Dadas las bolas de estos tres colores dispuestas aleatoriamente en una línea (el número real de bolas no importa), la tarea es organizarlas de manera que todas las bolas del mismo color estén juntas y sus grupos de colores colectivos estén en el orden correcto.
var array = [3, 3, 2, 1, 3, 2, 1],
MID = 2,
i = 0,
j = 0,
n = array.length - 1;
while (j <= n) {
if (array[j] < MID) {
[array[i], array[j]] = [array[j], array[i]];
i++;
j++;
} else if (array[j] > MID) {
[array[n], array[j]] = [array[j], array[n]];
n--;
} else {
j++;
}
}
console.log(array);Según yo, simplemente puede inicializar tres variables como 0 para los recuentos de cada 1 , 2 y 3 . Atraviese la matriz una vez e incremente el contador correspondiente en 1 para los valores en cada índice, es decir, si el valor en un índice particular es 2, incremente la segunda variable en 1.
Una vez que tenga los recuentos, el índice (Count1 - 1) th será la última aparición de 1, el índice (Count1 + Count2 - 1) th será la última aparición de 2 y (Count1 + Count2 + Count3 - 1) el índice será la última aparición de 3.
Puede recorrer toda la matriz y asignar los valores en consecuencia. De esta manera es algo así como Conteo ordenado pero, por supuesto, no es estable . Sin embargo, tiene otra opción como ya se mencionó en las respuestas anteriores: Problema de la bandera nacional holandesa
Puede contar el número de ocurrencias de 1, 2, 3 y usar esa información para recrear / obtener la matriz ordenada:
const arr = [3, 3, 2, 1, 3, 2, 1]
const count = arr.reduce((acc, curr) => {
acc[curr]++;
return acc;
}, {1: 0, 2: 0, 3: 0})
arr.forEach((_, j) => {
if (j < count[1])
arr[j] = 1
else if (j < count[1] + count[2])
arr[j] = 2
else
arr[j] = 3
})
console.log(arr)Debido al hecho de que sabe que la matriz puede contener solo 3 elementos, puede iterar sobre la matriz completa para cada uno de ellos (esto significa que el algoritmo se ejecuta 3 * n veces = {{ X0}}).
La restricción de espacio indica que debe trabajar en el lugar , es decir, trabajar en la matriz de entrada .
Esta es mi solución:]
function swap(i, j, arr) {
const currentVal = arr[j];
arr[j] = arr[i];
arr[i] = currentVal;
}
function sort(arr) {
let globalIndex = 0;
[1, 2, 3].forEach(item => {
for (let i = globalIndex; i < a.length; i++) {
if (arr[i] === item) {
swap(i, globalIndex, arr);
globalIndex++;
}
}
});
}
const a = [1, 2, 3, 2, 1, 1];
sort(a);
console.log(a);Preguntas relacionadas
Nuevas preguntas
javascript
Para preguntas sobre la programación en ECMAScript (JavaScript / JS) y sus diversos dialectos / implementaciones (excepto ActionScript). Incluya todas las etiquetas relevantes en su pregunta; por ejemplo, [node.js], [jquery], [json], etc.