¿Cómo encontrar el k-ésimo número más grande en sumas por pares como setA + setB?

Question

Aquí se establecen dos enteros, digamos A y B y podemos obtener otra serie C, en el que cada elemento es la suma del elemento a de A y B en B. elemento

Por ejemplo, A = {1, 2}, B = {3,4} y obtenemos C = {4, 5, 6} donde 4 = 1 + 3, 5 = 1 + 4 = 2 + 3, 6 = 2 + 4

Ahora yo desea saber qué número es el kth más grande en el conjunto C, por ejemplo, 5 es el segundo más grande en el ejemplo anterior.

¿Existe una solución eficiente?

Sé que la ordenación de sumas pairwise es un problema abierto y tiene un límite de tiempo n^2 menor. Pero dado que solo se necesita el k-ésimo número más grande, tal vez podamos aprender del algoritmo O (n) de encontrar el número medio en una matriz no ordenada.

Gracias.

Answer 1

Si k está muy cerca de 1 o N, cualquier algoritmo que genere las sumas ordenadas de forma perezosa podría simplemente ejecutarse hasta que aparezca el elemento kth o N-kth.

En particular, estoy pensando en la mejor búsqueda del siguiente espacio: (a, b) significa el elemento ath de A, la primera lista, añadida a la b desde B, la segunda.

Mantener en el mejor = los pares de cola de prioridad más baja (a, b) con costo (a, b) = A [a] + B [b].

Comience con solo (1,1) en la cola de prioridad, que es el mínimo.

Repeat until k items popped: 
pop the top (a,b) 
if a<|A|, push (a+1,b) 
if a=1 and b<|B|, push (a,b+1) 

Esto le da una conectividad peine de dientes de sierra y le evita tener que marcar cada uno (a, b) visitó en una matriz. Tenga en cuenta que el costo (a + 1, b)> = costo (a, b) y el costo (a, b + 1)> = costo (a, b) porque A y B están ordenados.

Aquí hay una foto de un peine para mostrar la regla de generación sucesora anterior (se inicia en la esquina superior izquierda; a es la dirección horizontal):

|------- 
|------- 
|------- 

Es simplemente la mejor primera exploración de (hasta) todos | A | * | B | tuplas y sus sumas.

Tenga en cuenta que la mayoría de los elementos posibles que se insertan antes de reventar k es 2 * k, porque cada elemento tiene 1 o 2 sucesores. Aquí está un posible estado de la cola, donde los artículos empujados a la cola están marcadas *:

|--*---- 
|-*----- 
*------- 

Todo por encima ya la izquierda de la frontera * ya se ha hecho estallar.

Para el caso , haga lo mismo pero con el orden de cola de prioridad invertido y el orden de exploración (o, simplemente niegue e invierta los valores, obtenga el valor (N-k) mínimo, luego niegue y devuelva la respuesta).

Véase también: lista ordenada de sumas por parejas on SO, o Open problems project.

Answer 2

Bueno, O (n) sería un límite inferior (probablemente no sea ajustado), de lo contrario podría ejecutar el algoritmo O (n) n veces para obtener una lista ordenada en O (n^2).

¿Puede asumir que los dos juegos están ordenados (los presenta en orden ordenado arriba)? Si es así, es posible que obtengas algo con un caso promedio que sea decentemente mejor haciendo una "salida anticipada", empezando en el último par de elementos, etc. Solo una corazonada.

Answer 3

ordenar matrices A & B: O (mlogm + nlogn) Aplicar una forma modificada del algoritmo para la fusión de 2 matrices según: O (m + n) es decir, en cada punto, u suma las los dos elementos. Cuando hayas obtenido (m + n-k + 1) el elemento th en C, deja de fusionar. Ese elemento es esencialmente el kth más grande. P. ej. {1,2} & {3,4}: Ordenar C: {1 + 3, (1 + 4) | (2 + 3), 2 + 4}