在一个 R 行 C 列的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解析：这是一个越往右下角数字越大的数组。那么我们可以从左下角或者右上角开始寻找。如果该数字小于要找的数字，那就往右找，不然就往上找。如果超出了数组的边界了还没找到，那就是没有这个数字。
答案：
//时间复杂度为 O(R+C)，空间复杂度为 O(1)
bool Find(const int* matrix, const int rows, const int columns, const int number)
{
if (nullptr==matrix || rows<=0 || columns<=0) return false;
int r=rows-1, c=0;
while (r>=0 && c<columns)
{
int pos = r*columns+c;
if (matrix[pos]==number) return true;
if (matrix[pos]>number) --r;
else ++c;
}
return false;
}
网友评论