Leetcode 378. K-й наименьший элемент в отсортированной матрице

Постановка задачи

Учитывая n x n matrix, где каждая из строк и столбцов отсортирована в порядке возрастания, возвращает самый маленький элемент kth наименьшего элемента в матрице.

Обратите внимание, что это kth наименьший элемент в порядке сортировки, а не kth отдельный элемент.

Вы должны найти решение со сложностью памяти лучше, чем O(n^2).

Тестовые случаи

Пример 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Пример 2:

Input: matrix = [[-5]], k = 1
Output: -5

Ограничения

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• Все строки и столбцы matrix гарантировано отсортированы в неубывающем порядке.
• 1 <= k <= n^2

Подход

Это еще один вариант поиска k-го наибольшего/наименьшего числа из заданного ввода. Небольшое изменение состоит в том, что вход представляет собой матрицу. В любом случае, мы все еще можем продолжить наш общий подход к поиску k-го наибольшего/наименьшего числа с использованием priorityqueue/heap.

Поскольку это поиск k-го наименьшего элемента в матрице, мы будем использовать maxHeap, и если вопрос касался k-го самого большого элемента в матрице, то это будет minHeap.

Алгоритм

1. Создайте maxHeap.
2. Пройдитесь по матрице и продолжайте добавлять элементы в maxHeap.
3. Если размер maxHeap становится больше, чем k, просто опросите самый верхний элемент и продолжите обход.
4. Наконец, верните любой элемент, присутствующий в верхней части кучи.

Сложность времени и пространства

Мы используем приоритетную очередь, которая сортирует добавляемый элемент в кучу + мы также проходим через матрицу. Таким образом, временная сложность будет O(n*nlog(n*n)) + O(n² * log(n²)) так как logn времени потребуется для добавления элемента в кучу.

Внутри maxheap будет храниться максимум K элементов, поэтому сложность нашего пространства будет O(K).

Код