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

Topic describes

Search two dimensional matrix

Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties:

  • The elements of each row are arranged in ascending order from left to right.
  • The elements of each column are arranged from top to bottom.

Example 1:

Input: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 5 output: trueCopy the code

Example 2:

Input: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 20 output: falseCopy the code

prompt

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • – 109 < =matix[i][j]< = 109
  • All elements in each row are arranged in ascending order from left to right
  • All elements in each column are arranged in ascending order from top to bottom
  • -109 <= target <= 109

Thought analysis

First of all, brute force cracking, but without the word efficient, we can choose dichotomy for optimization, because it’s already sorted matrix, we can traverse the diagonal of the matrix,

The code shown

Solution 1: Brute force cracking, time complexity O(mn){O(mn)}O(mn), space complexity O(1){O(1)}O(1).

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    return true; }}}return false;
    }
Copy the code

Solution 2: binary search, the matrix has been sorted, we need to use binary search to speed up our algorithm. Time complexity O(LG (n!) ){O(lg(n!) )}O(lg(n!) ), space complexity O(1){O(1)}O(1).

    private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length-1 : matrix.length-1;

        while (hi >= lo) {
            int mid = (lo + hi)/2;
            if (vertical) { // searching a column
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true; }}else { // searching a row
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true; }}}return false;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // iterate over matrix diagonals
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true; }}return false; 
    }
Copy the code

Method 3: time complexity O (m + n) (m + n)} {O O (m + n), space complexity O (1) (1)} {O O (1).

public boolean searchMatrix(int[][] matrix, int target) {
        // start our "pointer" in the bottom-left
        int row = matrix.length-1;
        int col = 0;

        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else { // found it
                return true; }}return false;
    }
Copy the code