requirements

Given an n x n matrix matrix, where each row and column elements are sorted in ascending order, find the KTH smallest element in the matrix. Notice that it is the KTH small element, not the KTH distinct element.

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 small element is 13Copy the code

Example 2:

Input: matrix = [[-5]], k = 1 Output: -5Copy the code

Tip:

  • n == matrix.length
  • n == matrix[i].length
  • 1 <= n <= 300
  • -109 <= matrix[i][j] <= 109
  • The problem data ensures that all rows and columns in the matrix are sorted in non-decreasing order
  • 1 <= k <= n2

The core code

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) - >int:
        m,n = len(matrix),len(matrix[0])
        l,r = matrix[0] [0],matrix[m - 1][n - 1]
        while l < r:
            count = 0
            mid = (r - l)// 2 + l
            for i in range(n):
                j  = n - 1
                while j >= 0 and matrix[i][j] > mid:
                    j -= 1
                count = count + j + 1
            if count >= k:
                r = mid
            else:
                l = mid + 1
        return l 
Copy the code

Another solution

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) - >int:
        tmp = []
        for i in matrix:
            tmp.extend(i)
        tmp.sort()
        return tmp[k - 1]
Copy the code

The first solution is to use the binary search method, but here we need to record our number, we need to be careful to take the maximum in a row, so that we can know whether to go straight down the row or to find back in this row, at this point we need to consider; The second solution: we directly flatten the two-dimensional matrix, sort the array, and finally directly take out the KTH digit.