El número único mínimo en una matriz se define como min{v|v occurs only once in the array} Por ejemplo, el número mínimo único de {1, 4, 1, 2, 3} es 2. ¿Hay alguna mucho mejor que ordenar?Encontrar el número único mínimo en una matriz
Creo que esta es una solución de O (N) en el tiempo y el espacio:
HashSet seenOnce; // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)
for each in input // O(N)
if item in seenMultiple
next
if item in seenOnce
remove item from seenOnce
add to item seenMultiple
else
add to item seeOnce
smallest = SENTINEL
for each in seenOnce // worst case, O(N)
if item < smallest
smallest = item
Si usted tiene una gama limitada de valores enteros, puede reemplazar los HashSets con BitArrays indexado por el valor.
Esto es genial, señor, pero ¿dónde puedo encontrar esta mágica función de hash de acceso aleatorio O (1) de la que usted habla? Por lo que yo (y el resto del mundo) sé que el "mejor" tiempo de acceso aleatorio para la función hash es O (logn). – ElKamina
A menos que me falta algo, no se necesita acceso aleatorio. El primer pase pasa por encima de 'input' (O (N)) y realiza búsquedas, inserciones y eliminaciones en los conjuntos de hash, cada O (1). Total: O (N). El segundo pase, como está escrito actualmente, gira sobre 'seenOnce', pero eso se soluciona fácilmente: simplemente vuelva a repetir' input' (O (N)), pruebe la membresía en 'seenOnce' (O (1)), y si está allí, añádalo a un nuevo 'seenOnceList' (O (1)), total O (N). Finalmente haga un escaneo para el mínimo, O (N). Net O (N), ¿no? – DSM
@ElKamina - Estás confundiendo un árbol con un hash. Consulte http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions y mire la lista debajo de O (1). Con una gran mesa y una función hash apropiada, las colisiones son insignificantes. – walrii
No es necesario hacer una clasificación completa. Realice un bucle interno de clasificación de burbujas hasta que obtenga un valor mínimo distinto en un extremo. En el mejor de los casos, esto tendrá una complejidad de tiempo O (k * n) donde k = número de valores mínimos no diferenciados. Sin embargo, la peor de las complicaciones es O (n * n). Por lo tanto, esto puede ser eficiente cuando el valor esperado de k < < n.
Creo que esta sería la complejidad de tiempo mínima posible a menos que pueda adaptar cualquier algoritmo de clasificación O (n * logn) a la tarea anterior.
"Mejor", que significa "menor complejidad de tiempo"? –
@VaughnCato: sí, me pregunto si podemos hacer mejor que O (nlogn). – shilk
¿El rango de sus valores es limitado o está restringido? Si son integrales con un rango restringido, creo que O (N) es posible. – walrii