Algoritmos de selección en matriz clasificada

esta es una pregunta de entrevista de google:

Dada una Matriz N * N. Todas las filas están ordenadas y todas las columnas están ordenadas. Encuentra el Kth. El elemento más grande de la matriz.

hacerlo en n ^ 2 es simple y podemos ordenarlo usando montones o tipos de combinación (n lg n) y luego obtenerlos, pero ¿hay un mejor enfoque, mejor que (n lg n)?

ejemplo de la matriz ::

1 5 7 12 3 6 8 14 4 9 10 15 11 17 19 20 

1 <5 <7 <12 y 1 <3 <4 <11 de manera similar las otras filas y columnas. ahora digamos que necesitamos encontrar el décimo elemento más pequeño, aquí es 11 … espero que esto agregue algún detalle a la pregunta …

Sí, hay un algoritmo O (K) debido a Frederickson y Johnson.

Greg N. Frederickson y Donald B. Johnson. Selección generalizada y clasificación: matrices ordenadas . SIAM J. Comput. 13, pp. 14-30. http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no

Con la matriz dada en el ejemplo: si desea buscar el 7º elemento, sabe que el 7º elemento está en los elementos M [4] [1..4], M [1..4] [ 4]. Obtiene dos matrices ya ordenadas, 12,14,15,20 y 11,17,19 que se pueden fusionar. Luego aplica una búsqueda binaria que es O (log N).

Generalizar: para el k-ésimo elemento más grande de esta matriz, debe seleccionar la capa adecuada: [2N-1] + [2 (N-1) -1] + …> = k para que el algoritmo seleccione el nivel adecuado La capa a buscar es Sum [2 (Ni) -1]> = k, para i = 0, N-1, donde i es el número de la capa. Después de encontrar i, el número de capa, tendrá 2 elementos (Ni) -1 en esa matriz que deben fusionarse y luego buscarse. La complejidad para buscar esa capa es O (log [2 (Ni) -1] = O (log (Ni)) …

La progresión aritmética conduce a

0> = i ^ 2-2 * N * i + k

i1,2 = N + -sqrt (N ^ 2-k), donde k es el elemento que buscamos …

Como todo está ordenado, puede hacer una búsqueda en diagonal. (Aunque, francamente, no sé lo que significa que “todas las filas están ordenadas y todas las columnas están ordenadas”. Si eso es cierto literalmente, simplemente vaya al elemento k-ésimo en una enumeración diagonal de la matriz).

gira la matriz en el sentido de las agujas del reloj 45 grados. Obtendrá un conjunto de datos en forma de diamante. La altura será 2N-1, el número de elementos en cada fila desde arriba será como: 1,2,3,4,5,4,3,2,1 para una N = 5

Descubrirá que cada número en una fila es siempre más grande que cualquier número anterior.

para la fila k-ésima (contando desde 1), tendrá k elementos para k = N k pertenece a {1..2N-1}

Al calcular el número acumulado de elementos de la fila 1 a k-1 y de 1 a k, encontrará la fila donde se ubica su objective (sum (1 a k-1)

Ahora que ha localizado una fila de elementos con el peor caso N total. Puede ordenarlos y luego encontrar el correcto. esto toma O (N ln N)

dado que N = sqrt (n), el costo total de este algoritmo es O (sqrt (n) ln (sqrt (n)))

Basado en N, puede encontrar la diagonal donde se encuentra el elemento. Por ejemplo en la matriz,

  1 5 7 12 3 6 8 14 4 9 10 15 11 17 19 20 

Puede deducir la diagonal determinando el número total de elementos en las diagonales anteriores,

 /diagonal#/elements/# of elements/cumulative # of elements/ /d1/ 1 / 1 / 1 / /d2/ 3 5 / 2 / 1+2 = 3 / /d3/ 4 6 7 / 3 / 1+2+3 = 6 / /d4/ 11 9 8 12 / 4 / 1+2+3+4 = 10 / /d5/ 17 10 14 / 3 / /d6/ 19 15 / 2 / /d7/ 20 / 1 / 

La razón por la que necesitamos encontrar la diagonal es porque las diagonales anteriores siempre tendrán elementos menores que cualquiera de los elementos diagonales actuales y las diagonales a continuación siempre tendrán elementos mayores que cualquiera de los elementos diagonales actuales.

Por lo tanto, puede estar seguro de que la diagonal d4 tiene el elemento requerido (dado que contiene el séptimo más grande al décimo más grande). Desde que hasta la diagonal anterior había 6 elementos, solo necesitas encontrar el cuarto elemento más grande en diagonal d4 .

Haces una primera búsqueda de aliento comenzando en (0,0). (0,0) ‘s 2 niños (0,1) y (1,0) se agregan a la lista de candidatos potenciales para el 2 ° elemento. Bucle seleccionando el elemento más pequeño en la lista de posibles candidatos para ser el siguiente elemento, agregue sus hijos a la lista de candidatos potenciales. Deténgase cuando encuentre el elemento kth.

Haga que los candidatos potenciales incluyan un montón mínimo. El montón nunca será mayor que n + m.

También podría hacer lo inverso desde el último elemento (n, m) si k es mayor que n * m / 2.

Peor caso: esto sería n * m / 2 lg (n + m), en lugar de n * m lg (n * m) de clasificación.

Puede encontrar el k ésimo elemento más pequeño en el tiempo O (n log n) esperado, si observa que:

  1. Generando un número aleatorio que se encuentra entre Array [i] [j] y Array [k] [l] tal que Array [i] [j]

Usando [1] como una subrutina, puede usar un procedimiento similar a SELECCIÓN ALEATORIA para generar el k ésimo número más pequeño en toda la matriz.

Mi código a continuación es un algoritmo O (k). No funciona en un caso de borde determinado (probablemente uno en cada dirección: xey). Enumeré el borde del caso para que alguien pueda arreglarlo. No voy a arreglarlo porque es hora de dormir para mí.

Resumen del algoritmo: solo necesita hacer un seguimiento de dos candidatos # que podrían ser los más pequeños, uno mientras avanza en la dirección xy uno mientras avanza en la dirección y. Piénselo y podría tener sentido para usted.

 enum Direction { X, Y }; struct Index { Index(int unsigned x, int unsigned y) : x(x), y(y) {} void operator = (Index const & rhs) { x = rhs.x; y = rhs.y; } int unsigned x; int unsigned y; }; int unsigned solve(int unsigned i_k, int unsigned ** i_data, int unsigned i_n) { if (1 == i_k) { return i_data[0][0]; } Direction dir = X; Index smaller(0,0); Index larger(0,0); if (i_data[1][0] < i_data[0][1]) { dir = X; smaller = Index(1,0); larger = Index(0,1); } else { dir = Y; smaller = Index(0,1); larger = Index(1,0); } for (int unsigned i = 0; i < (i_k - 2); ++i) { int unsigned const x = smaller.x; int unsigned const y = smaller.y; if (X == dir) { if ((x + 1) == i_n) { // End of row smaller = larger; larger.x += 1; dir = Y; } else if (i_data[x + 1][y] < i_data[larger.x][larger.y]) { smaller.x += 1; } else { smaller = larger; larger = Index(x + 1, y); dir = Y; } } else { if ((y + 1) == i_n) { // End of col smaller = larger; larger.y += 1; dir = X; } else if (i_data[x][y + 1] < i_data[larger.x][larger.y]) { smaller.y += 1; } else { smaller = larger; larger = Index(x, y + 1); dir = X; } } } return i_data[smaller.x][smaller.y]; } 

no funciona en el siguiente caso marginal (donde llegamos al final de una fila). Me voy a la cama, siéntete libre de arreglar este caso:

  size = 4; data = createMatrix(size); data[0][0] = 1; data[1][0] = 6; data[2][0] = 10; data[3][0] = 11; data[0][1] = 3; data[1][1] = 7; data[2][1] = 12; data[3][1] = 14; data[0][2] = 4; data[1][2] = 8; data[2][2] = 13; data[3][2] = 15; data[0][3] = 5; data[1][3] = 9; data[2][3] = 19; data[3][3] = 20; answer = solve(14, data, size); assertAnswer(answer, 15, ++testNum); deleteMatrix(data, size); 

La siguiente es mi solución C ++, que se basa en un montón mínimo. Cuando una celda en la matriz está en la parte superior del montón mínimo, el número a la derecha y / o el lado negativo se insertará en el montón.

 #include  #include  #include  using namespace std; struct Entry { int value; int x; int y; bool operator < (const Entry& other) { return this->value > other.value; } }; bool getKthNumber(int* matrix, int row, int col, int k, int* result){ if(matrix == NULL || row <= 0 || col <= 0 || result == NULL) return false; if(k <= 0 || k > row * col) return false; vector minHeap; Entry first = {matrix[0], 0, 0}; minHeap.push_back(first); make_heap(minHeap.begin(), minHeap.end()); for(int i = 0; i < k; ++i){ first = minHeap[0]; int x = first.x; int y = first.y; if(first.y == 0 && first.x < row - 1){ Entry next = {matrix[(x + 1) * col], x + 1, y}; minHeap.push_back(next); push_heap(minHeap.begin(), minHeap.end()); } if(first.y < col - 1){ Entry next = {matrix[x * col + y + 1], x, y + 1}; minHeap.push_back(next); push_heap(minHeap.begin(), minHeap.end()); } pop_heap(minHeap.begin(), minHeap.end()); minHeap.pop_back(); } *result = first.value; return true; }