This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Write an efficient algorithm to determine whether there is a target value in an M x n matrix. The matrix has the following characteristics:

The integers in each row are arranged in ascending order from left to right. The first integer in each line is greater than the last integer in the previous line.

Example 1: input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 output: true https://leetcode-cn.com/problems/search-a-2d-matrixCopy the code

Thought analysis

• The problem is easy to understand and can be solved in many ways.
• First of all, we can use HashMap to search and solve efficiently in space for time. The disadvantage is that it does not take advantage of the matrix features suggested by the question.
• Two binary search can also be adopted, while using the characteristics of matrix, improve the query efficiency. Advantages: No extra space, high query efficiency.

AC code

• A HashMap solution

public class DayCode {
    public static void main(String[] args) {
        int[][] matrix = {{1.3.5.7}, {10.11.16.20}, {23.30.34.60}};
        int target = 3;
        boolean ans = new DayCode().searchMatrix(matrix, target);
        System.out.println(ans);
    }


    /** * Time complexity O (m * n) * space complexity O (m * n) *@param matrix
     * @param target
     * @return* /
    public boolean searchMatrix(int[][] matrix, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) { map.put(matrix[row][col], matrix[row][col]); }}returnmap.containsKey(target); }}Copy the code

• Binary search method

public class DayCode {
    public static void main(String[] args) {
        int[][] matrix = {{1.3.5.7}, {10.11.16.20}, {23.30.34.60}};
        int target = 3;
        boolean ans1 = new DayCode().searchMatrix1(matrix, target);
        System.out.println(ans1);
    }

    /** * Time complexity O(log (m + n)) * space complexity O(1) *@param matrix
     * @param target
     * @return* /
    public boolean searchMatrix1(int[][] matrix, int target) {
        int rowIdx = binarySearchFirstColumn(matrix, target);
        if (rowIdx < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIdx], target);
    }

    private boolean binarySearchRow(int[] matrix, int target) {
        int left = 0, right = matrix.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (matrix[mid] == target) {
                return true;
            } else if (matrix[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1; }}return false;
    }

    private int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1; }}returnlow; }}Copy the code

Submit tests:

conclusion

• The time complexity O (m * n) and space complexity O (m * n) of HashMap solution
• The time complexity O(log (m + n)) and space complexity O(1) of binary search solution
• Stick to the daily question, come on!