12 - Hard - Kth Smallest Elemen

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

示例:

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

返回 13。
说明:
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

时间超限！！！

class Solution:
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        n = len(matrix)
        pointer = [0 for _ in range(n)]
        sorted_list = []
        for _k in range(k):
            _min = matrix[-1][-1]
            cur = -1
            for i in range(start, n):
                if pointer[i] < n and matrix[i][pointer[i]] < _min:
                    _min = matrix[i][pointer[i]]
                    cur = i
            pointer[cur] += 1
            sorted_list.append(_min)
        return sorted_list[-1]

二分查找法

import bisect

class Solution:
    def kthSmallest(self, matrix, k):
        """
        二分查找
        将查找上下限设为矩阵的右下角与左上角元素，查找过程中对中值在矩阵每一行的位置进行累加，记该值为loc，根据loc与k的大小关系调整上下限
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        if not matrix or len(matrix) == 0:
            return None
        low, high = matrix[0][0], matrix[-1][-1]
        while low <= high:
            mid = low + (high - low) // 2  # 中值
            loc = sum(bisect.bisect_right(i, mid) for i in matrix)  # 
            if loc >= k:
                high = mid - 1
            else:
                low = mid + 1
        return low

题目中例子的运行过程如下

low   high   mid    loc  bisect.bisect_right(i, mid) for i in matrix
1      15     8      2      [2 0 0]
9      15     12     6      [3 2 1]
13     15     14     8      [3 3 2]
13     13     13     8      [3 3 2]
13     12

优先队列

class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        m, n = len(matrix), len(matrix[0])
        q = [(matrix[0][0], 0, 0)]
        ans = None
        for _ in range(k):
            ans, i, j = heapq.heappop(q)
            if j == 0 and i + 1 < m:
                heapq.heappush(q, (matrix[i + 1][j], i + 1, j))
            if j + 1 < n:
                heapq.heappush(q, (matrix[i][j + 1], i, j + 1))
        return ans