在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。
灵感来得很快,马上就猜到是通过比较大小来对row和col加加减减来取得target,但是一开始选错了起始节点——选择了左上角开始,被测试用例按在地上摩擦。稍微做了草稿以后从左下开始,然后又是一套临界值的测试用例组合拳把我打得鼻青脸肿,最后缝缝补补还是ac了,蛤蛤,顺便get到了“std::ios::sync_with_stdio(false);”黑科技。
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
std::ios::sync_with_stdio(false);
int len=matrix.size();//列
if(len==0)
{
return false;
}
int h_len=matrix[0].size();//行
if(h_len==0)
{
return false;
}
int row=h_len-1;
int col=0;
while(col<len&&row>=0)
{
if(target>matrix[col][row])
{
col++;
}
else if(target<matrix[col][row])
{
row--;
}
else
{
return true;
}
}
return false;
}