剑指offer 4# 表中找数

在一个 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;
    
}