Python 中排序矩阵的第 K 小元素

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

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

  • 定义一个名为 checkVal() 的方法，其参数为矩阵和值
  • i := 0，j := matrix[0] 的长度 - 1，counter := 0
  • 当 i < 矩阵的长度且 j >= 0 时
    • 如果 matrix[i, j] > value，则将 j 减 1，否则 counter := counter + j + 1，将 i 加 1
  • 返回 counter
  • 主方法将如下所示 -
  • n := 矩阵的行数，high := 右下角元素，low := 左上角元素
  • 当 low <= high 时，执行
    • mid = low + (high – low)/2
    • count := checkVal(matrix, mid)
    • 如果 count < k，则 low := mid + 1，否则 high := mid – 1
  • 返回 low

让我们看一下以下实现，以便更好地理解 -

示例

 在线演示

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

更新于: 2020年4月30日

348 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告