Python中排序矩阵中的Kth个最小元素

假设我们有一个xn矩阵，其中的行和列均按升序排序，我们必须找到矩阵中第k个最小的元素。请注意，它是排序顺序中的第k个最小元素，而不是第k个唯一元素。因此，如果输入像[[1,5,9]，[10,11,13]，[12,13,15]]，则如果k = 8，则输出将为13。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为checkVal()的方法，参数为矩阵和值

• i：= 0，j：=矩阵[0] – 1的长度，计数器：= 0

• 当i <矩阵长度且j> = 0时

• 如果matrix [i，j]> value，则将j减1，否则counter：= counter + j + 1，将i加1

• 返回柜台

• 主要方法将是-

• n：=矩阵行，高：=右下角元素，低：=左上角元素

• 当低<=高时，

• 中=低+（高–低）/ 2

• 计数：= checkVal（矩阵，中）

• 如果计数<k，则低：=中+1，否则高：=中– 1

• 返回低

让我们看下面的实现以更好地理解-

示例

class Solution(object):
   def kthSmallest(self, matrix, k):
      """
      :type matrix: List[List[int]]
      :type k: int
      :rtype: int
      """
      n = len(matrix)
      high = matrix[n-1][n-1]
      low = matrix[0][0]
      while low<=high:
         mid = low + (high - low) /2
         count = self.check_value(matrix,mid)
         if count< k:
            low = mid+1
         else :
            high = mid-1
      return int(low)
   def check_value(self, matrix, value):
      i = 0
      j = len(matrix[0])-1
      counter = 0
      while(i<len(matrix) and j >=0):
         if matrix[i][j] > value:
            j-=1
         else:
            counter+=j+1
            i+=1
      return counter
matrix = [[1,5,9],[10,11,13],[12,13,15]]
ob = Solution()
print(ob.kthSmallest(matrix, 8))

输入值

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

输出结果

13