Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending 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]], the Output target = 5: 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]], the Output target = 20: falseCopy the code

Constraints:

  • m == matrix.length

  • n == matrix[i].length

  • 1 <= n, m <= 300

  • -109 <= matix[i][j] <= 109

  • All the integers in each row are sorted in ascending order.

  • All the integers in each column are sorted in ascending order.

  • -109 <= target <= 109

    package com.array;

    / * *

    • @Author you guess
    • @Date 2021/1/10 21:28
    • @ Version 1.0
    • @Desc

    */ public class Leetcode_240_Searcha2DMatrixII {

    /** * 2021/1/10; /** * 2021/1/10; /** * 2021/1/10; /** * 2021/1/10 10 ms, faster than 24.15% of Java online submissions for Search a 2D Matrix II. * Memory Usage: 51.3 MB, Less than 8.84% of Java online submissions for Search of a 2D Matrix II public boolean searchMatrix(int[][] matrix, int target) { int rows = matrix.length; int columns = matrix[0].length; int topRow = 0; for (int i = rows - 1; i >= 0; i--) { if (matrix[i][columns - 1] < target) { topRow = i; break; } } int bottomRow = rows - 1; for (int i = 0; i < rows; i++) { if (matrix[i][0] > target) { bottomRow = i - 1; break; } } for (int i = topRow; i <= bottomRow; i++) { if (binarySearch(matrix, target, i)) { return true; } } return false; }//searchMatrix public boolean binarySearch(int[][] matrix, int target, int row) { int head = 0; int tail = matrix[0].length - 1; while (head <= tail) { int mid = (head + tail) / 2; if (matrix[row][mid] == target) { return true; } else if (matrix[row][mid] < target) { head = mid + 1; } else { tail = mid - 1; } } return false; } /** * 2020-01-10, Methods 2 * Reference to the upper right corner of the element as a benchmark 】 【 https://leetcode.com/problems/search-a-2d-matrix-ii/discuss/1001740/JAVA-oror-O (m % 2 bn) - oror - Easy - to - underst And * use the lower left corner as the benchmark, tar is bigger than the current element to look right, tar is smaller than the current element to look up! Given in the Java online submissions for Search of a 2D Matrix II. Each node in the Java online submission list is linked to the linked node in the linked list. Search a 2D Matrix 【Runtime: * * @param target * @return */ public Boolean searchMatrix2(int[][] matrix, int target) { int row = matrix.length - 1; int col = 0; while (row >= 0 && col < matrix[0].length) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] > target) { row--; } else {col++; // Target is larger than it, on the right}} return false; } public static void main(String[] args) { Leetcode_240_Searcha2DMatrixII main = new Leetcode_240_Searcha2DMatrixII();Copy the code

    // System.out.println(main.searchMatrix(new int[][]{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, }, {18, 21, 23, 26, 30}} //, 5)); //true

    // System.out.println(main.searchMatrix2(new int[][]{{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, }, {18, 21, 23, 26, 30}} //, 14); //true

    System.out.println(main.searchMatrix2(new int[][]{{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}}, 20); //false }Copy the code

    }

Method 2 is shared! Search a 2D Matrix [Runtime: 0 ms, faster than 100.00%]