seleccion por ordenamiento metodos insercion ejemplos algoritmos algorithm

algorithm - metodos - ordenamiento por seleccion java



Algoritmos de selección en matriz ordenada. (9)

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 elemento Kth más grande de la matriz.

hacerlo en n ^ 2 es simple y podemos clasificarlo utilizando el ordenamiento de pila o combinación (n lg n) y luego obtenerlo, 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 a las otras filas y columnas. Ahora digamos que necesitamos encontrar el décimo elemento más pequeño, aquí es 11 ... esperemos que esto agregue algún detalle a la pregunta ...

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]. Obtienes dos matrices ya ordenadas, 12,14,15,20 y 11,17,19 que se pueden fusionar. A continuación, se aplica una búsqueda binaria que es O (registro N).

Generalizar: para k-th el elemento más grande en esta matriz, debe seleccionar la capa adecuada: [2N-1] + [2 (N-1) -1] + ...> = k para que el algoritmo seleccione el apropiado la capa a buscar es Suma [2 (Ni) -1]> = k, para i = 0, N-1, donde i es el número de la capa. Después de que encuentre i, el número de capa, tendrá 2 (Ni) -1 elementos en esa matriz que deben combinarse 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 ...

Gire la matriz en sentido horario 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 un N = 5

Descubrirá que cada número en una fila siempre es más grande que cualquier otro de los números anteriores.

para la fila k-th (contando desde 1), tendrá k elementos para k <N y, 2N-k para k> = N k pertenece a {1..2N-1}

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

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

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

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 <vector> #include <algorithm> #include <functional> 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<Entry> 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; }

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: x e y). Enumeré el caso de borde para que alguien pueda arreglarlo. No lo voy a arreglar porque es hora de irme a la cama.

Resumen del algoritmo: solo necesita realizar un seguimiento de dos números candidatos que pueden ser los más pequeños, uno mientras avanza en la dirección x y otro mientras avanza en la dirección y. Piénsalo y podría tener sentido para ti.

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 perimetral (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);

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

  1. Generar un número aleatorio que se encuentra entre el Array [i] [j] y el Array [k] [l] de tal manera que el Array [i] [j] <Array [k] [l] toma O (n) tiempo (esperado) y

Utilizando [1] como una subrutina, puede usar un procedimiento similar a RANDOMIZED-SELECT para generar el k ésimo número más pequeño en toda la matriz.

Sobre la base de 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 siguientes 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 (ya que contiene la séptima más grande a la décima más grande). Desde hasta la diagonal anterior había 6 elementos, solo necesitas encontrar el cuarto elemento más grande en diagonal d4 .

Usted hace una primera búsqueda de aliento a partir de la (0,0). (0,0) Los 2 hijos (0,1) y (1,0) se agregan a la lista de candidatos potenciales para el segundo elemento. Seleccione el elemento más pequeño en la lista de candidatos potenciales para ser el siguiente elemento, agregue sus hijos a la lista de candidatos potenciales. Deténgase cuando encuentre el elemento kth.

Haga que la lista de candidatos potenciales sea un montón mínimo. El montón nunca será más grande que n + m.

También puede hacer lo contrario del ú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.

Ya que todo está ordenado, puedes hacer una búsqueda 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-th en una enumeración diagonal de la matriz).