leetcode:剑指offer----二维数组中查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例：

面对这样的问题第一反应是暴力搜索吧！使用两个循环遍历每个元素，这样的话时间复杂度就是O(N*M)。思考一秒钟这肯定不是最优的，开始发现规律，左上角的元素是最小的，右下角的元素是最大的，右上角和左下角的元素在某个方向上最大，在另一个方向最小。具体的实现思路下面再说。

• C++解答思路：

拿到题经过思考以后，想到了使用vector中的find函数在每一行中搜索元素，在不考虑vector的find函数的时间复杂度下，该方法的时间复杂度为O(N)。

bool findNumberIn2DArray(vector>& matrix, int target) {
        int flag = -1;
        if(matrix.size() == 0)
        {
            return false;
        }
        for (auto mat:matrix)
        {
            if (find(mat.begin(),mat.end(),target) != mat.end())
            {
                flag = 1;
                break;
            }
            else
            {
                flag = 0;
                continue;
            }
        }
        if(flag)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

根据左下角和右上角元素的特性，假设从右上角开始搜索，然后根据大小决定向大的方向或者向小的方向移动。

bool findNumberIn2DArray(vector>& matrix, int target) {
        int rows = matrix.size();
        if (rows==0)
        {
            return false;
        }
        int cols = matrix.at(0).size();
        if(cols == 0)
        {
            return false;
        }
        int row = rows-1,col = 0,flag = 0;
        while (row >= 0 && col < cols)
        {
            int val = matrix.at(row).at(col);
            if(val < target)
            {
                col += 1;
            }
            else if(val > target)
            {
                row -= 1;
            }
            else
            {
                flag = 1;
                break;
            }
        }
        if (flag)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

两种方法的用时都为24ms

• python解答思路：

python的解答思路和C++第二种一样。

 def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        row,col = len(matrix) - 1,0
        flag = 0
        while row >= 0 and col < len(matrix[0]):
            val = matrix[row][col]
            if val > target:
                row -= 1
            elif val < target:
                col += 1
            elif val == target:
                flag = 1
                break
        if flag:
            return True
        else:
            return False