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