二维数组的查找

在一个 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;
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。