Учитывая матрицу тревог, где каждая из строк и столбцов отсортирована в порядке возрастания, найдите k-й наименьший элемент в матрице

Question

Существует O (kLogN) решение этого с использованием кучи. В худшем случае k = N ^ 2.таким образом, сложность времени становится O (N ^ 2LogN).Есть ли лучший алгоритм для этой проблемы.