Dados dos arreglos ordenados de números, queremos encontrar el par con la quinta suma más grande posible. (Un par es un elemento de la primera matriz y un elemento de la segunda matriz). Por ejemplo, con matrices.

[2, 3, 5, 8, 13][4, 8, 12, 16]

Las parejas con mayores sumas son

13 + 16 = 2913 + 12 = 258 + 16 = 2413 + 8 = 218 + 12 = 20

Así que el par con la cuarta suma más grande es (13, 8). ¿Cómo encontrar el par con la kth suma más grande posible?

Además, ¿cuál es el algoritmo más rápido? Las matrices ya están ordenadas y los tamaños M y N.

Ya estoy al tanto de laO (Klogk) solución, utilizando Max-Heap dadoaquí .

También es uno de los favoritos.Google pregunta de la entrevista, y exigen unaO (k) solución .

También he leído en alguna parte que existe unaDe acuerdo) Solución, que soy incapaz de averiguar.

Alguien puede explicar la solución correcta con un pseudocódigo.

PD Por favor no publiqueesta enlace como respuesta / comentario. NO contiene la respuesta.