leetcode378.有序矩阵中第K小的元素_n*n矩阵,找到行最大列最小的元素,时间复杂度是多少,如何优化

378.有序矩阵中第K小的元素(中等)

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第k小元素，而不是第k个元素。

示例：

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。
1
2
3
4
5
6
7
8

说明：

你可以假设 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

解法二：

把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
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23