378。有序矩阵中第K小的元素题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix题目目标给定一个nxn的矩阵，每一行都有元素和列按升序排序，找到矩阵中第k个最小的元素。请注意，它是排序后第k个最小的元素，而不是第k个不同的元素。示例：矩阵=[[1,5,9],[10,11,13],[12,13,15]],k=8,返回13。提示：您可以假设k的值始终有效,1≤k≤n2。解题思路是先审题。题目中给出了二维数组，该题需要求的是二维数组中第k小的元素。这里，最直接的方法就是将二维数组转化为一维数组，并将转化后的一维数组按升序排序，那么此时一维数组中的第k个元素就是想要的结果.代码大致如下：#pythondefkthSmallest(self,matrix:List[List[int]],k:int)->int:res=[]forrowinmatrix:foreleinrow:res.append(ele)水库。sort()returnres[k-1]这里，代码没有使用矩阵的特性。而是转换为一维数组进行求解。这个方案的时间复杂度是O(n^2logn)，也就是对nxn个数进行排序。因为上面的解法是将矩阵转化为一维数组，并不是在矩阵的基础上解决问题。下面使用二分查找，尝试在矩阵的前提下分析和回答问题。思路：二分查找考虑使用二分查找的原因，因为题目中说到矩阵中，每一行每一列的元素都是按升序排列的。也就是说，题目给的矩阵中，元素是从左上向右下递增的，根据例子展开分析：例子：matrix=[[1,5,9],[10,11,13],[12,13,15]],k=8将上面的例子稍微展开如下（只是为了更方便的展示二分查找法的效果）：matrix=[[1,5,9,10,11],[10,11,13,14,15],[12,13,15,16,17],[13,14,16,17,18],[14,18,22,26,30]],k=8将上面的二维数组转化为下图：我们假设左上角的元素为matrix[0][0],右下角的元素为矩阵[n-1][n-1]。根据题意和上图，我们可以知道。matrix[0][0]是二维数组中的最小值，matrix[n-1][n-1]是最大值。我们现在用二分查找的方法来分析，设matrix[0][0]和matrix[n-1][n-1]分别为left和right。现在我们尝试取mid(left<=mid<=right)，可以发现矩阵中小于等于mid值的元素会分布在矩阵的左上部分，而大于mid的元素比中间值分布在矩阵的右下部分。比如下图，此时取mid为15：这里将大于mid和小于等于mid的元素分成两部分，两者沿着红色的分界线分开。至此，我们可以看到有多少元素大于mid，小于等于mid。这里分析一下上面红色分割线的划分依据：因为每行每列的元素都是按升序排列的，所以在我们前面的分析中，元素需要和mid进行比较。比如我们现在要求元素分布在left部分，也就是元素值小于等于mid的部分。此时我们可以考虑从左下角开始，到右上角寻找。这使得能够快速减小范围。具体过程如下：从左下角开始，向右上角扩散。如果当前位置的元素值小于等于mid值，则表示从当前位置往上的所有元素都小于等于mid（因为每一列都是升序排列的），记录当前的个数元素计数，注意维护和更新。这时，当元素值小于或等于mid值时，向右移动，再次比较。否则，向上移动，寻找稍小的元素进行比较，直到移动到边界。这里取中值除法的时候，按照上面的方法，可以判断出小于等于k的个数，那么就会出现下面两种情况：当count大于等于k的时候，那么这个数你要找的可以确定答案在[left,mid]这边；否则，答案在[mid+1,right]区间。然后按照这个思路，循环，直到找到答案。关于二分查找法的执行过程，可以看下面这个简单的图（不懂的可以画图帮助理解）：具体代码实现如下。代码实现类解决方案：defkthSmallest(self,matrix:List[List[int]],k:int)->int:defsearch(mid,n):#从左下角到右上角搜索i,j=n-1,0#统计小于等于mid的元素个数count=0whilei>=0andj
