Быстрый поиск n-го по величине продукта в большой матрице чисел

Я работаю над алгоритмом сортировки/ранжирования, который работает с довольно большим количеством элементов, и мне нужно реализовать следующий алгоритм эффективным способом, чтобы заставить его работать :

Есть два списка номеров. Они одинаково длинные, около 100-500 тысяч штук. Из этого мне нужно найти n-й самый большой продукт между этими списками, т.е. если вы создаете матрицу, где сверху у вас есть один список, сбоку у вас есть другой, и каждая ячейка является произведением числа выше и числа сбоку.

Пример: списки: A=[1, 3, 4]и B=[2, 2, 5]. Тогда произведения будут [2, 2, 5, 6, 6, 15, 8, 8, 20]. Если бы я хотел, чтобы 3-е по величине из них было 8.

Наивным решением было бы просто сгенерировать эти числа, отсортировать их, а затем выбрать n-е по величине. Но это O(m^2 * log m^2), где m — количество элементов в небольших списках, и это просто недостаточно быстро.

Я думаю, что мне нужно сначала отсортировать два небольших списка. То есть O(m * log m). Тогда я точно знаю, что самый большой A[0]*B[0]. Второй по величине — либо A[0]*B[1], либо A[1]*B[0], ...

Я чувствую, что это можно сделать в O(f(n))шагов, не зависящих от размера матрицы. Но я не могу найти эффективный способ сделать эту часть.

Изменить: был удален ответ, в котором предлагалось запомнить позицию в двух отсортированных наборах, а затем посмотреть на A[a]*B[b+1] и A[a+1]*B[b] , возвращая больший и увеличивая a/b. Я собирался опубликовать этот комментарий до того, как его удалили:

Это не сработает. Представьте два списка A=B=[3,2,1]. Это даст вам матрица вида [9,6,3 ; 6,4,2 ; 3,2,1]. Итак, вы начинаете с (0,0)=9, переходите к (0,1)=6, а затем выбор (0,2)=3 или (1,1)=4. Однако это будет пропустите (1,0)=6, что больше обоих. Таким образом, вы не можете просто смотреть на два соседа, но вы должны вернуться.