球类网站如何做宣传,天津建设工程信息网上网流程,荣誉章标志做网站,塘厦基础网站建设文章目录1. 题目2. 解题2.1 按列遍历2.2 二分查找2.3 合并k个有序链表1. 题目
给你一个矩阵 mat#xff0c;其中每一行的元素都已经按 递增 顺序排好了。 请你帮忙找出在所有这些行中 最小的公共元素。
如果矩阵中没有这样的公共元素#xff0c;就请返回 -1。
示例#x…
文章目录1. 题目2. 解题2.1 按列遍历2.2 二分查找2.3 合并k个有序链表1. 题目
给你一个矩阵 mat其中每一行的元素都已经按 递增 顺序排好了。 请你帮忙找出在所有这些行中 最小的公共元素。
如果矩阵中没有这样的公共元素就请返回 -1。
示例
输入mat [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
输出5提示
1 mat.length, mat[i].length 500
1 mat[i][j] 10^4
mat[i] 已按递增顺序排列。来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-smallest-common-element-in-all-rows 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 按列遍历
按列遍历计数最先达到行数的就是答案
class Solution {
public:int smallestCommonElement(vectorvectorint mat) {int m mat.size(), n mat[0].size();int count[10001] {0};for(int j 0, i; j n; j){for(i 0; i m; i){if(count[mat[i][j]] m)return mat[i][j];}}return -1;}
};180 ms 24.2 MB
2.2 二分查找
依次对第一行的每个元素在其他行进行二分查找都找到了就是答案
代码略
2.3 合并k个有序链表
类似的思想
class Solution {
public:int smallestCommonElement(vectorvectorint mat) {int m mat.size(), n mat[0].size(), i 0, cur mat[0][0], count 1;vectorint idx(m,0);//每行遍历到的位置while(1){i (i1)%m;//循环遍历每行while(idx[i] n mat[i][idx[i]] cur)idx[i];//找curif(idx[i] n)//找完了没找到return -1;else if(mat[i][idx[i]]cur){ //找到了count;idx[i];}else if(mat[i][idx[i]] cur){ //没找到那就以当前数重新找cur mat[i][idx[i]];count 1;idx[i];}if(count m)//出现m次的返回return cur;}return -1;}
};200 ms 24.4 MB 长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
