Search in the two-dimensional array of leetcode sword offer (10)

Title Description

In a n * m In a two-dimensional array , Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete an efficient function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Example :

The existing matrix matrix as follows ：

[
    [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]
]

Given target = 5, return  true.

Given  target = 20, return  false.

Coding ideas

The idea of depth first traversal of graph , You can also use the width of the graph to traverse the idea first , You can do it yourself .

Python3 Code implementation

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        def isvalid(matrix, i, j):
            #  Control boundaries 
            if len(matrix) == 0:
                return False
            h = len(matrix) - 1
            w = len(matrix[0]) - 1
            if i >=0 and i <= h and j >=0 and j <= w:
                return True
            return False

        def isVisited(visited, i, j):
            #  Have you been visited before 
            if not visited[i][j]:
                visited[i][j] = True
                return True
            return False

        def dfs(matrix, target, visited,i, j):
            #  Depth first traversal implementation 
            if isvalid(matrix, i, j) and isVisited(visited, i, j):
                if matrix[i][j] == target:
                    return True
                if matrix[i][j] > target:
                    return dfs(matrix, target, visited, i, j-1) or dfs(matrix, target, visited, i-1, j)
                if matrix[i][j] < target:
                    return dfs(matrix, target, visited, i, j+1) or dfs(matrix, target, visited, i+1, j)
            return False
        if len(matrix) == 0:
            return False
        visited = [[False] * len(matrix[0]) for _ in range(len(matrix))]
        return dfs(matrix, target, visited, 0, 0)

C++ Code implementation

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0)
            return false;
        vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
        return dfs(matrix, visited, target, 0, 0);
    }
public:
    bool isValid(vector<vector<int>>& matrix, int i, int j){
        if(matrix.size() == 0)
            return false;
        int h = matrix.size() - 1;
        int w = matrix[0].size() - 1;
        if(i>=0 && i<=h && j>=0 && j<=w)
            return true;
        return false;
    }
public:
    bool isVisited(vector<vector<bool>>& visited, int i, int j){
        if(!visited[i][j]){
            visited[i][j] = true;
            return true;
        }
        return false;
    }
public:
    bool dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int target, int i, int j){
        if(isValid(matrix, i, j) && isVisited(visited, i, j)){
            if(matrix[i][j] == target)
                return true;
            if(matrix[i][j] > target)
                return dfs(matrix, visited, target, i, j-1) || dfs(matrix, visited, target, i-1, j);
            if(matrix[i][j] < target)
                return dfs(matrix, visited, target, i, j+1) || dfs(matrix, visited, target, i+1, j);
        }
        return false;
    }
};