leetcode [378] 有序矩阵中第K小的元素

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

示例:

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

返回 13。

说明:

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

来自题解:

二分查找，最小值第一个，最大值最后一个，mid为中间值，统计小于等于mid的数量，如果小，low = mid + 1，否则high = mid

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        def count(target, l):
            i = 0
            j = l-1
            counter = 0
            while j >= 0 and i < l:
                if matrix[i][j] <= target:  #!!! 小于等于，必须包含相等，即便等于目标值的数量
                    counter += j + 1
                    i += 1
                else:
                    j -= 1
            return counter
        
        low = matrix[0][0]
        n = len(matrix)
        high = matrix[n-1][n-1]
        while low < high:
            mid = (high + low) // 2
            c = count(mid, n)    # O(N)
            if c < k:    # 包含相等的数量小于k，才将中间值加1
                low = mid + 1
            else:
                high = mid
        return high