给你一个矩阵 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int smallestCommonElement(vector<vector<int>>& 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
代码略
类似的思想
class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size(), i = 0, cur = mat[0][0], count = 1;
vector<int> idx(m,0);//每行遍历到的位置
while(1)
{
i = (i+1)%m;//循环遍历每行
while(idx[i] < n && mat[i][idx[i]] < cur)
idx[i]++;//找cur
if(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