arrays - una - vectores en java ejemplos

Encuentra la mediana de la suma de las matrices.

Question

Se dan dos matrices ordenadas de longitud n y la pregunta es encontrar, en tiempo O ( n ), la mediana de su matriz de suma, que contiene todas las posibles sumas por pares entre cada elemento de la matriz A y cada elemento de la matriz B.

Por ejemplo: Sean A [2,4,6] y B [1,3,5] las dos matrices dadas. La matriz de suma es [2+1,2+3,2+5,4+1,4+3,4+5,6+1,6+3,6+5] . Encuentra la mediana de esta matriz en O ( n ).

Resolver la pregunta en O ( n ^ 2 ) es bastante sencillo, pero ¿hay alguna solución O ( n ) para este problema?

Nota: esta es una pregunta de entrevista que se le hizo a uno de mis amigos y el entrevistador estaba bastante seguro de que se puede resolver en O ( n ) vez.

Answer 1

¿No funciona esto ?:

Puede calcular el rango de un número en tiempo lineal siempre que A y B estén ordenados. La técnica que utiliza para calcular el rango también se puede usar para encontrar todas las cosas en A+B que se encuentran entre algún límite inferior y algún límite superior en el tiempo lineal del tamaño de la salida más |A|+|B| .

Muestra aleatoriamente n cosas de A+B Toma la mediana, di foo . Calcula el rango de foo . Con probabilidad constante, el rango de foo está dentro de n del rango de la mediana. Sigue haciendo esto (un número constante de veces esperado) hasta que tengas límites superiores e inferiores en la mediana que estén dentro de 2n uno del otro. (Todo este proceso toma el tiempo lineal esperado, pero obviamente es lento).

Todo lo que tiene que hacer ahora es enumerar todo entre los límites y hacer una selección de tiempo lineal en una lista de tamaño lineal.

(Relacionado, no disculparía al entrevistador por hacer una pregunta de entrevista obviamente tan desagradable. Cosas como estas no indican en modo alguno su capacidad para codificar).

EDITAR : Puedes calcular el rango de un número x haciendo algo como esto:

Set i = j = 0.
While j < |B| and A[i] + B[j] <= x, j++.
While i < |A| {
  While A[i] + B[j] > x and j >= 0, j--.
  If j < 0, break.
  rank += j+1.
  i++.
}

EDICIÓN ADICIONAL : En realidad, el truco anterior solo reduce el espacio candidato a aproximadamente n miembros (log) de A+B Entonces tiene un problema de selección general dentro de un universo de tamaño n registro (n); puede hacer básicamente el mismo truco una vez más y encontrar un rango de tamaño proporcional al registro (n) sqrt (n) donde realiza la selección.

Aquí le explicamos por qué: si muestra k objetos de un conjunto n y toma la mediana, entonces el orden de la mediana de la muestra está entre (1/2 - sqrt (log (n) / k)) th y el (1/2 + sqrt (log (n) / k)) th elementos con al menos una probabilidad constante. Cuando n = | A + B |, queremos tomar k = sqrt (n) y obtenemos un rango de aproximadamente sqrt (n log n) elementos --- eso es aproximadamente | A | log | A |. Pero luego lo haces de nuevo y obtienes un rango del orden de sqrt (n) polylog (n).

Answer 2

Debe usar un algoritmo de selección para encontrar la mediana de una lista sin clasificar en O (n). Mira esto: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Answer 3

Digamos que las matrices son A = {A[1] ... A[n]} , y B = {B[1] ... B[n]} , y la matriz de suma por pares es C = {A[i] + B[j], where 1 <= i <= n, 1 <= j <= n} que tiene n^2 elementos y necesitamos encontrar su mediana.

La mediana de C debe ser un elemento de la matriz D = {A[1] + B[n], A[2] + B[n - 1], ... A[n] + B[1]} : si corriges A[i] , y consideras todas las sumas A[i] + B[j] , verías que el único A[i] + B[j = n + 1 - i] (que es uno de D ) Podría ser la mediana. Es decir, puede que no sea la mediana, pero si no lo es, todos los demás A[i] + B[j] tampoco son la mediana.

Esto se puede probar considerando todos B[j] y cuente el número de valores que son más bajos y el número de valores que son mayores que A[i] + B[j] (podemos hacerlo con bastante precisión porque las dos matrices están ordenadas - El cálculo es un pensamiento un poco desordenado). Vería que para A[i] + B[n + 1 - j] estas dos cuentas son las más "balanceadas".

El problema se reduce entonces a encontrar la mediana de D , que tiene solo n elementos. Un algoritmo como el de Hoare''s funcionará.

ACTUALIZACIÓN : esta respuesta es incorrecta. La conclusión real aquí es que la mediana es uno de los elementos de D , pero luego la mediana de D no es la misma que la de C

Answer 4

La solución O (n) correcta es bastante complicada y requiere una cantidad significativa de texto, código y habilidad para explicar y probar. Más precisamente, se necesitan 3 páginas para hacerlo de manera convincente, como se puede ver en detalles aquí cse.yorku.ca/~andy/pubs/X+Y.pdf (encontrado por simonzack en los comentarios).

Básicamente es un inteligente algoritmo de dividir y vencer que, entre otras cosas, aprovecha el hecho de que en una matriz ordenada n por n, uno puede encontrar en O(n) la cantidad de elementos que son más pequeños / mayores que un número dado k . Desglosa de forma recursiva la matriz en submatrices más pequeñas ( al tomar solo las filas y columnas impares, dando como resultado una submatriz que tiene n/2 columnas y n/2 filas ) que combinada con el paso anterior, resulta en una complejidad de O(n) + O(n/2) + O(n/4)... = O(2*n) = O(n) . Es una locura

No puedo explicarlo mejor que el documento, por lo que explicaré una solución más simple, O(n logn) lugar :) .

Solución O (n * logn):

¡Es una entrevista! No puedes obtener esa solución O(n) a tiempo. Entonces, hey, ¿por qué no proporcionar una solución que, aunque no sea óptima, muestre que puede hacerlo mejor que los otros candidatos obvios de O(n²) ?

Haré uso del algoritmo O(n) mencionado anteriormente, para encontrar la cantidad de números que son más pequeños / mayores que un número dado k en una matriz ordenada n-by-n . ¡Tenga en cuenta que no necesitamos una matriz real! La suma cartesiana de dos arreglos de tamaño n , como lo describe el OP, da como resultado una matriz ordenada n-by-n , que podemos simular considerando los elementos del arreglo de la siguiente manera:

a[3] = {1, 5, 9};
b[3] = {4, 6, 8};
//a + b:
{1+4, 1+6, 1+8,
 5+4, 5+6, 5+8,
 9+4, 9+6, 9+8}

Por lo tanto, cada fila contiene números no decrecientes, y también lo hace cada columna. Ahora, imagina que te dan un número k . Queremos encontrar en O(n) cuántos de los números en esta matriz son más pequeños que k , y cuántos son mayores. Claramente, si ambos valores son menores que (n²+1)/2 , ¡eso significa que k es nuestra mediana!

El algoritmo es bastante simple:

int smaller_than_k(int k){
    int x = 0, j = n-1;
    for(int i = 0; i < n; ++i){
        while(j >= 0 && k <= a[i]+b[j]){
            --j;
        }
        x += j+1;
    }
    return x;
}

Básicamente, esto cuenta cuántos elementos se ajustan a la condición en cada fila. Dado que las filas y columnas ya están ordenadas como se ve arriba, esto proporcionará el resultado correcto. Y como i y j repiten como máximo n veces, el algoritmo es O(n) [ Tenga en cuenta que j no se restablece dentro del bucle for ]. El algoritmo greater_than_k es similar.

Ahora, ¿cómo elegimos k ? Esa es la parte logn . ¡Búsqueda binaria! Como se ha mencionado en otras respuestas / comentarios, la mediana debe ser un valor contenido dentro de esta matriz:

candidates[n] = {a[0]+b[n-1], a[1]+b[n-2],... a[n-1]+b[0]}; .

Simplemente ordene esta matriz [también O(n*logn) ], y ejecute la búsqueda binaria en ella. Dado que la matriz ahora está en orden no decreciente, es sencillo notar que la cantidad de números más pequeños que cada candidate[i] también es un valor no decreciente (función monotónica), lo que lo hace adecuado para la búsqueda binaria . El número más grande k = candidate[i] cuyo resultado smaller_than_k(k) más pequeño que smaller_than_k(k) devuelve más pequeño que (n²+1)/2 es la respuesta, y se obtiene en las iteraciones log(n) :

int b_search(){
    int lo = 0, hi = n, mid, n2 = (n²+1)/2;
    while(hi-lo > 1){
        mid = (hi+lo)/2;
        if(smaller_than_k(candidate[mid]) < n2)
            lo = mid;
        else
            hi = mid;
    }
    return candidate[lo]; // the median
}