Leetcode (Sword finger offer) - 04. search in two-dimensional array

Topic link ： Click to open the link

The main idea of the topic ： A little

Their thinking

Related enterprises

• Bytes to beat
• Microsoft （Microsoft）
• Google （Google）
• Apple （Apple）
• Amazon （Amazon）
• Oracle （Oracle）
• tencent （Tencent）
• Facebook
• Hang Seng Electronics Co., Ltd

AC Code

• Java

//  Solution (1)
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length)
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
}

//  Solution (2)
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int rowLen = matrix.length;
        if (rowLen == 0 || matrix[0].length == 0) {
            return false;
        }
        
        //  Every time  row  Judge whether it is possible to implement ,  If you can perform binary search 
        for (int i = 0; i < matrix.length; i++) {
            if (target < matrix[i][0] || target > matrix[i][matrix[i].length - 1]) {
                continue;
            }
            int idx = find(matrix[i], target);
            if (matrix[i][idx] == target) {
                return true;
            }
        }
        return false;
    }

    private int find(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l - 1;
    }
}

• C++

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int i = matrix.size() - 1, j = 0;
        while(i >= 0 && j < matrix[0].size())
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
};