【python-leetcode378-二分查找】有序矩阵中的第k小元素

发布时间：2020-12-20 09:54:09 所属栏目：Python 来源：网络整理

导读：给定一个?n x n?矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。 ? 示例: matrix = [ [ 1,5,9], [10,11,13], [12,13,15] ], k = 8, 返回 13。 ? 提示：你可以假设 k 的值永远

给定一个?n x n?矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例:

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

返回 13。
?

提示：
你可以假设 k 的值永远是有效的,1 ≤ k ≤ n2?。

以上面的矩阵为例：

让左指针l指向第一个元素1，右指针r指向最后一个元素15，也就是l=1,r=15，那么最大值和最小值之间的中值就是(r-l)/2+l=(15-1)/2+1=8。然后从后往前依次计算比中值大的次数。具体看代码。

class Solution(object):
    def kthSmallest(self,matrix,k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        m,n =len(matrix),len(matrix[0])
        l,r =matrix[0][0],matrix[m-1][n-1]
        while l<r:
            count=0
            mid=(r-l)//2+l
            for i in  range(n):
                j=n-1
                while j>=0 and matrix[i][j]>mid:
                    j-=1
                count=count+j+1
            if count>=k:
                r=mid
            else:
                l=mid+1
        return l

如若取点巧：

[]
         matrix:
            tmp.extend(i)
        tmp.sort()
        return tmp[k-1]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!