关键词：
-
第一种方法：将二维矩阵中的数存起来，然后排序输出第k个，耗时较多
class Solution
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
vector<int>v;
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
v.push_back(matrix[i][j]);
sort(v.begin(),v.end());
return v[k-1];
;
-
第二种方法：利用二分，左上角的数最小，右下角的数最大，取个mid，然后在矩阵中找出小于等于mid的数cnt
-
如果cnt<k，则说明小于等于mid的数的个数不足k个，那么令左端为mid+1,向右找，直到找到小于等于mid的数为k个，那么此时的L就是答案；
-
当cnt>=k的时候，说明小于等于mid的数已经超过k了，mid比我们要求的数肯定大，那么将右端点为mid即可，在左边查找。
-
至于怎么找矩阵中小于等于mid的个数，我们可以从矩阵左下角开始找，当该位置的数<=mid，此时cnt+=i+1，
就是该列第i行的上面的所有的元素都小于等于mid，累加即可，同时列指针j++;
如果该位置的数大于了mid，那么只要将行指针向上i--即可。复杂度比第一种方法小得多，耗时短。
class Solution
public:
bool check(vector<vector<int>>& matrix,int mid,int k)
int n=matrix.size();
int i=n-1,j=0;
int cnt=0;
while(i>=0&&j<n)
if(matrix[i][j]<=mid)
cnt+=i+1;
j++;
else
i--;
return cnt<k;
int kthSmallest(vector<vector<int>>& matrix, int k)
int n=matrix.size();
int L=matrix[0][0],R=matrix[n-1][n-1];
while(L<R)
int mid=(L+R)>>1;
if(check(matrix,mid,k))
L=mid+1;
else
R=mid;
return L;
;
378.有序矩阵中第k小的元素normal二分查找
题目:给你一个 nxn 矩阵 matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。示例1：输入：matrix=[[1,5,9],[10,11,13],[12,13,15]],k&#... 查看详情
378.有序矩阵中第k小的元素(代码片段)
给定一个 nxn 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。 示例：matrix=[[1,5,9],[10,11,13],[12,13,15]],k=8,返回13。解:这个题很有意思，找... 查看详情
378.有序矩阵中第k小的元素(代码片段)
378.有序矩阵中第K小的元素给你一个nxn矩阵matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。输入：matrix=[[1,5,9],[10,11,13],[12,13,1... 查看详情
378kthsmallestelementinasortedmatrix有序矩阵中第k小的元素
给定一个nxn矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个元素。示例:matrix=[ [1, 5, 9], [10,11,13], [12,13,15]],k=8,返回13。说明:你可... 查看详情
leetcode刷题100天—378.有序矩阵中第k小的元素(优先队列)—day16(代码片段)
前言：作者：神的孩子在歌唱大家好，我叫运智给你一个nxn矩阵matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。示例1&#x... 查看详情
378.有序矩阵中第k小的元素(代码片段)
一、题目描述给你一个nxn矩阵matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。你必须找到一个内存复杂度优于O(n^2)的解决方案。示... 查看详情
leetcode中等378有序矩阵中第k小的元素(代码片段)
给你一个nxn矩阵matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。你必须找到一个内存复杂度优于O(n2)的解决方案。示例1：输入&#... 查看详情
力扣有序矩阵中第k小的元素(代码片段)
给定一个 nxn 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是排序后的第k小元素，而不是第k个不同的元素。 示例：matrix=[[1,5,9],[10,11,13],[12,13,15]],k=8,返回13。来源：力扣（LeetCode）链... 查看详情
有序数组中第k小的数字(代码片段)
...然过了。。。因为矩阵在行列方向上都是升序排列的，在有序数组中搜索一个数字常用二分法，所以可以考虑变种的二分法。二维数组从左下向右上搜索，每次搜索检查一下当前搜遍历到数字范围有没有超过k。代码暴力：importja... 查看详情
03k个数或第k个数算法
面试题17.09.第k个数面试题17.14.最小K个数378.有序矩阵中第K小的元素剑指OfferII061.和最小的k个数对剑指OfferII076.数组中的第k大的数字485.最大连续1的个数1004.最大连续1的个数III4.寻找两个正序数组的中位数两个有序数组中找第k大的... 查看详情
03k个数或第k个数算法
面试题17.09.第k个数面试题17.14.最小K个数378.有序矩阵中第K小的元素剑指OfferII061.和最小的k个数对剑指OfferII076.数组中的第k大的数字485.最大连续1的个数1004.最大连续1的个数III4.寻找两个正序数组的中位数两个有序数组中找第k大的... 查看详情
找轮转后的有序数组中第k小的数
...组中没有相同的数，原排列顺序是递增排列。在轮转后的有序数组中查找最小数的算法如下：intfindIndexOfMin(intnum[],intn){intl=0;intr=n-1;while(l<=r){intmid=l+(r-l)/2;if(num[mid]>num 查看详情
leetcode练习(python)：二分查找类：第230题：二叉搜索树中第k小的元素：给定一个二叉搜索树，编写一个函数 kthsmallest 来查找其中第 k
题目：二叉搜索树中第K小的元素：给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第k个最小的元素。 说明：你可以假设k总是有效的，1≤k≤二叉搜索树元素个数。 思路：二叉搜索树具有良好的性质，一个... 查看详情
leetcode练习(python)：二分查找类：第230题：二叉搜索树中第k小的元素：给定一个二叉搜索树，编写一个函数 kthsmallest 来查找其中第 k
题目：二叉搜索树中第K小的元素：给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第k个最小的元素。 说明：你可以假设k总是有效的，1≤k≤二叉搜索树元素个数。 思路：二叉搜索树具有良好的性质，一个... 查看详情
9.27在两个排序数组中找到第k小的数
【题目】： 给定两个有序数组arr1和arr2，再给定一个整数k，返回所有的数中第K小的数 举例： arr1=[1,2,3,4,5]，arr2=[3,4,5]，k=1 1是所有数中第1小的数，所以返回1 arr1=[1,2,3]，arr2=[3,4,5,6]，k=4 3... 查看详情
数据结构数组笔记
...数组并不属于线性结构。数组是由类型相同的数据构成的有序集合数组中的元素本身可以具有某种结构，而且元素的结构相同。数组中的元素可以是一个单一的元素，也可以是一个线性表，因此数组可以看做一般线性表的推广。... 查看详情
快速排序算法及其思想的应用（寻找一个序列中第k小元素）(代码片段)
...对这两部分采用同样的算法递归处理，最终使得序列有序。关键就在于这个特定的算法，具体实现起来，我们可以取序列中任意一个元素作为媒介，并把比其小的数字放在这个元素左边，把比其大的数字放在... 查看详情
230.二叉搜索树中第k小的元素
230.二叉搜索树中第K小的元素题意给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第k个最小的元素。你可以假设k总是有效的，1≤k≤二叉搜索树元素个数。解题思路中序遍历，利用Python3中提供的生成器方法；中序... 查看详情