攜手創作,共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第9天,點擊查看活動詳情
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with a memory complexity better than O(n^2).
Example 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
復制代碼Example 2:
Input: matrix = [[-5]], k = 1
Output: -5
復制代碼Note:
n == matrix.length == matrix[i].length
1 <= n <= 300
-10^9 <= matrix[i][j] <= 10^9
All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
1 <= k <= n^2
復制代碼根據題意,給定一個 n x n 矩陣 matrix ,where each row and column is sorted in ascending order,Returns the first in the matrix k 個最小的元素. 請注意,它是排序順序中的第 k 個最小元素,而不是第 k 個不同的元素. And the question asks to find a space complexity better than O(n^2) 的解決方案.
The dumbest way is definitely to use space complexity O(n^2) 的方法,First sort both are an ordered list,Then take the k 個元素.我們使用另一種方法,Because each row is ordered,We can consider popping one minimum value from the matrix at a time,Then pop up the first k element must be the result we want,Here we will use the small root heap data structure.
時間復雜度位 O(klogN) ,如果 k 為 N^2 那麼時間復雜度為 O(N^2logN),空間復雜度為 O(N) ,
class Solution(object):
def kthSmallest(self, matrix, k):
""" :type matrix: List[List[int]] :type k: int :rtype: int """
M = len(matrix)
N = len(matrix[0])
L = [(matrix[i][0],i,0) for i in range(M)]
heapq.heapify(L)
for _ in range(k-1):
_, x,y = heapq.heappop(L)
if y!=N-1:
heapq.heappush(L, (matrix[x][y+1], x, y+1))
return heapq.heappop(L)[0]
復制代碼Runtime: 293 ms, faster than 51.00% of Python online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 17.4 MB, less than 85.38% of Python online submissions for Kth Smallest Element in a Sorted Matrix.
復制代碼leetcode.com/problems/kt…
您的支持是我最大的動力
