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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个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

以上是 Python中排序矩阵中的Kth个最小元素 的全部内容， 来源链接： utcz.com/z/338550.html

回到顶部