Necesito encontrar un algoritmo altamente optimizado para ordenar una matriz que consta de solo 0s n 1s.algo muy optimizado para ordenar una matriz que consta de solo 0s n 1s
Mi versión de la solución es contar el no. de ceros (decir x) y unos (decir y). Una vez que hagas eso, coloca x ceros en la matriz seguida por y 1s. Esto lo convierte en O (n).
¿Algún problema que funcione mejor que este ??? Me hicieron esta pregunta en una entrevista.
Dado que debe examinar cada uno de los elementos de entrada n, no puede mejorar el O(n).
Además, dado que su algoritmo requiere O(1) de memoria, tampoco puede mejorar eso (no hay nada mejor que O(1) asintóticamente).
Si suma la matriz, podría tener el número de 1, un poco más eficiente, pero igual O (n).
No puede ser más eficiente que O (N) porque cada artículo necesita ser inspeccionado.
¿De qué tipo de "matriz" estamos hablando? Si tuviéramos que contar los bits en un entero sin signo de 16 bits, entonces se han desarrollado varios algoritmos de tiempo O (1): ver Fast Bit Count Routines.
Este es uno de los algoritmos presentados allí; el que llaman el conteo paralelo Nifty:
#define MASK_01010101 (((unsigned int)(-1))/3)
#define MASK_00110011 (((unsigned int)(-1))/5)
#define MASK_00001111 (((unsigned int)(-1))/17)
int bitcount (unsigned int n) {
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101);
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011);
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111);
return n % 255 ;
}
estaba hablando de una matriz simple .. – akaHuman
no podemos hacer nada mejor que O (n), pero parece que podemos hacer en una sola pasada
low = 0;
high = arr.length - 1;
while (low < high) {
while (arr[low] == 0) {
low ++;
}
while (arr[high] == 1) {
high --;
}
if (low < high) {
//swap arr[low], arr[high]
}
}
Esto suena como una sola barra de ábaco tipo. Ahora tengo curiosidad por saber quién era su entrevistador.
Tienes que escanear la matriz completa una vez. Eso lo hace O (n). No creo que ningún otro algoritmo pueda mejorar O (n). – Vikas