赞
踩
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。
请注意,它是排序后的第k小元素,而不是第k个元素。
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n^2 。
用二分法,high是右下角,low是左上角,每次遍历矩阵,看小于等于mid的数count是多少,如果count<k,说明这个数在[mid+1,high]之间,如果count>=k,说明这个数在[low,mid]之间,最后当low==high时,就是第k小的元素。
class Solution(object): def kthSmallest(self, matrix, k): """ :type matrix: List[List[int]] :type k: int :rtype: int """ def counter(target, n): i = 0 j = n-1 count = 0 while i<n and j>=0: if matrix[i][j] <= target: count += j+1 #从右上角开始遍历如果它小了,那么它左边所有的都小 i += 1 else: j -= 1 return count n = len(matrix) low = matrix[0][0] high = matrix[n-1][n-1] while low < high: mid = low + (high - low)//2 count = counter(mid, n) if count < k: low = mid+1 else: high = mid return low
把n行矩阵看成n个递增的有序数组,可以设置n个指针,指向每个数组的第一个元素,把最小的取出来,之后那个指针加一,但是每次N个取最小,时间复杂度需要O(N),有没有更小的复杂度?
堆或优先队列不就是解决这种问题的方案嘛。维护一个N大小的最小堆,这样每次pop最小的,只需要logN。
所以维护一个最小堆,把每个数组目前最小的元素放到最小堆里,依次pop出来,之后Push它后面的那个元素,第k个pop的就是所求,注意当某一行pop完了之后就不需要push操作了。
class Solution(object): def kthSmallest(self, matrix, k): """ :type matrix: List[List[int]] :type k: int :rtype: int """ import heapq n = len(matrix) heap = [] heapq.heapify(heap) for i in range(min(k, n)): heapq.heappush(heap, (matrix[i][0], i, 0)) counter = 0 x, i, j = 0, 0, 0 while counter<k: counter += 1 x, i, j = heapq.heappop(heap) if j<n-1: # 如果j大于等于n-1了,说明这一行都已经遍历完了,直接从剩下的里面继续弹出就好了。 heapq.heappush(heap, (matrix[i][j+1], i, j+1)) return x
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。