在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解法很巧妙的一道题. 从左下角或右上角出发. 例如从左下角开始, 他的右边一定比他大, 他的上面一定比他小, 因此可以通过逐次移动行或列的方法寻找. 时间复杂度为O(n)
最讨厌的是...题目没有说matrixSize代表行数..我还以为是总元素数,尼玛调试了半天!
bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target){
if(matrixSize == 0)return false;
int i = matrixSize-1;
int j = 0;
while(i>=0 && (j < (*matrixColSize)))
{
if(matrix[i][j]>target) i--;
else if(matrix[i][j]< target ) j++;
else return true;
}
return false;
}
网友评论