Python 中排序矩阵中第 K 个最小元素
pythonserver side programmingprogramming
假设我们有一个 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
- while i <矩阵长度且 j >= 0
- 如果 matrix[i, j] > 值，则将 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
