Algoritmo para encontrar k números más pequeños en una matriz de n elementos

Intento escribir un algoritmo que pueda imprimir los k números más pequeños en una matriz n-size en el tiempo O (n), pero no puedo reducir la complejidad del tiempo a n. ¿Cómo puedo hacer esto?

Lo he hecho en una entrevista anterior, y una de las maneras más elegantes / eficientes de hacerlo es

O(n log k). with space: O(k) (thanks, @Nzbuu) 

Básicamente vas a usar un montón máximo de tamaño limitado a k. Para cada elemento del conjunto, verifique si es más pequeño que el máximo (solo O (1)). Si es así, ponlo en el montón (O (log k)) y elimina el máximo. Si es más grande, ve al siguiente artículo.

Por supuesto, el montón no produce una lista ordenada de k elementos, pero eso se puede hacer en O (k log k) que es fácil.

Del mismo modo, puede hacer lo mismo para encontrar los elementos k más grandes, en cuyo caso usaría un montón mínimo.

necesitará encontrar el elemento k más pequeño usando ‘algoritmo de selección’, que es O (n), y luego iterar la matriz de nuevo y devolver cada elemento que sea más pequeño / igual a él.
algoritmo de selección: http://en.wikipedia.org/wiki/Selection_algorithm
Tendrás que prestar atención si tienes repeticiones: tendrás que asegurarte de que no estás devolviendo más elementos que k (es posible si, por ejemplo, tienes 1,2, …, k, k, k, …). .)

EDITAR:
el algoritmo completo, y devolver una lista, según lo solicitado: deje que la matriz sea A

  1. find the k'th element in A using 'selection algorithm', let it be 'z' 2. initialize an empty list 'L' 3. initialize counter<-0 4. for each element in A: 4.1. if element < z: 4.1.1. counter<-counter + 1 ; L.add(element) 5. for each element in A: 5.1. if element == z AND count < k: 5.1.1. counter<-counter + 1 ; L.add(element) 6. return L 

observe aquí que se requiere una tercera iteración si su lista puede tener duplicados. si no puede, no es necesario, simplemente cambie la condición en 4.1 a <=.
también tenga en cuenta: L.add está insertando un elemento en una lista vinculada y por lo tanto es O (1).

Suponiendo que intenta mostrar los K números más pequeños, puede usar el algoritmo de selección de Hoare para encontrar el k ésimo número más pequeño. Eso divide la matriz en números más pequeños, el número késimo y los números más grandes.

Esto se puede hacer en tiempo lineal esperado (O (n)). Primero encuentre el kth elemento más pequeño de la matriz (usando el método de partición pivote para encontrar el estadístico kth ) y luego simplemente recorra el ciclo para verificar qué elementos son menores que el kth elemento más pequeño. Tenga en cuenta que esto funciona correctamente solo para elementos distintos.

Aquí está el código en c:

  /*find the k smallest elements of an array in O(n) time. Using the Kth order statistic-random pivoting algorithm to find the kth smallest element and then looping through the array to find the elements smaller than kth smallest element.Assuming distinct elements*/ #include  #include  #include  #define SIZE 10 #define swap(X,Y) {int temp=X; X=Y; Y=temp;} int partition(int array[], int start, int end) { if(start==end) return start; if(start>end) return -1; int pos=end+1,j; for(j=start+1;j<=end;j++) { if(array[j]<=array[start] && pos!=end+1) { swap(array[j],array[pos]); pos++; } else if(pos==end+1 && array[j]>array[start]) pos=j; } pos--; swap(array[start], array[pos]); return pos; } int order_statistic(int array[], int start, int end, int k) { if(start>end || (end-start+1) 

Es posible encontrar los k elementos más pequeños de n en O(n) tiempo (con lo cual quiero decir verdadero tiempo O(n) , no O(n + some function of k) ). Consulte el artículo de Wikipedia “Algoritmo de selección” , especialmente las subsecciones sobre “clasificación parcial desordenada” y “selección mediana como estrategia pivote”, y también para el artículo “Mediana de medianas” para la pieza esencial que hace esta O(n) .

La mejor solución posible al problema es la siguiente. Usa la ordenación rápida para encontrar pivotes y descartar la parte donde no se encuentra este elemento k, y recursivamente encontrar el siguiente pivote. (Es kth Max Finder, necesitas cambiar la condición if else para convertirlo en kth Min Finder). Aquí está el código JavaScript-

  // Complexity is O(n log(n)) var source = [9, 2, 7, 11, 1, 3, 14, 22]; var kthMax = function(minInd, MaxInd, kth) { // pivotInd stores the pivot position // for current iteration var temp, pivotInd = minInd; if (minInd >= MaxInd) { return source[pivotInd]; } for (var i = minInd; i < MaxInd; i++) { //If an element is greater than chosen pivot (ie last element) //Swap it with pivotPointer element. then increase ponter if (source[i] > source[MaxInd]) { temp = source[i]; source[i] = source[pivotInd]; source[pivotInd] = temp; pivotInd++; } } // we have found position for pivot elem. // swap it to that position place . temp = source[pivotInd]; source[pivotInd] = source[MaxInd]; source[MaxInd] = temp; // Only try to sort the part in which kth index lies. if (kth > pivotInd) { return kthMax(pivotInd + 1, MaxInd, kth); } else if (kth < pivotInd) { return kthMax(minInd, pivotInd - 1, kth); } else { return source[pivotInd]; } } // last argument is kth-1 , so if give 2 it will give you, // 3rd max which is 11 console.log(kthMax(0, source.length - 1, 2)); 

No sé exactamente lo que estás buscando, pero el tiempo O (n * k) es muy simple y el espacio O (k). Esta es la K más grande, por lo que tendría que dejarla caer.

Para el bruto por min de k (resultado) puede sustituir un montón

 private int[] FindKBiggestNumbersM(int[] testArray, int k) { int[] result = new int[k]; int indexMin = 0; result[indexMin] = testArray[0]; int min = result[indexMin]; for (int i = 1; i < testArray.Length; i++) { if(i < k) { result[i] = testArray[i]; if (result[i] < min) { min = result[i]; indexMin = i; } } else if (testArray[i] > min) { result[indexMin] = testArray[i]; min = result[indexMin]; for (int r = 0; r < k; r++) { if (result[r] < min) { min = result[r]; indexMin = r; } } } } return result; } 

Simplemente ordena la matriz con Merge Sort y luego imprime el primer número k, tomará n * log2 (n) en el peor de los casos.

¿Qué tal si usamos un Heap para almacenar los valores? Este costo es n cuando revisa cada valor en la matriz.

Luego vaya a través del Heap para obtener los valores k más pequeños.

El tiempo de ejecución es O (n) + O (k) = O (n)

Por supuesto, el espacio de memoria ahora es O (n + n)

Como se mencionó, hay dos formas de lograr dicha tarea:

1) Puede ordenar toda la matriz de n elementos con quicksort , heapsort o cualquier algoritmo de clasificación O (n log n) que desee, y luego seleccionar los m valores más pequeños en su matriz. Este método funcionará en O(n log n) .

2) Puede usar el algoritmo de selección para encontrar los elementos más pequeños en su matriz. Tomará O(n) tiempo para encontrar el k-ésimo valor más pequeño, ya que iterará este algoritmo m veces, el tiempo total será mx O(n) = O(n) .

Otra técnica: use el algoritmo QuickSelect y el resultado serían todos los elementos a la izquierda del resultado devuelto. La complejidad del tiempo promedio sería O (n) y en el peor de los casos sería O (n ^ 2). La complejidad del espacio sería O (1).