Вот два набора целых чисел, скажем, A и B, и мы можем получить другой набор C, в котором каждый элемент является суммой элемента a в A и элемента b в B.

Например, A = {1,2}, B = {3,4}, и мы получаем C = {4, 5, 6}, где 4 = 1 + 3 ， 5 = 1 + 4 = 2 + 3, 6 = 2 + 4

Теперь я хочу выяснить, какое число является k-ым по величине в множестве C, например, 5 является 2-ым по величине в приведенном выше примере.

Есть ли эффективное решение?

Я знаю, что попарная сортировка сумм является открытой проблемой и имеет ограничение по времени n ^ 2. Но поскольку требуется только k-е наибольшее число, возможно, мы сможем извлечь из алгоритма O (n) поиск среднего числа в несортированном массиве.

Благодарю.