【Java】【Leetcode】Search a 2D Matrix II

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 = [[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]], target = 5
Output: true

Example 2:

Input: matrix = [[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]], target = 20
Output: false

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

我们观察题目中给的那个例子，我们可以发现有两个位置的数字很有特点，左下角和右上角的数。左下角的18，往上所有的数变小，往右所有数增加，那么我们就可以和目标数相比较，如果目标数大，就往右搜，如果目标数小，就往上搜。这样就可以判断目标数是否存在。当然我们也可以把起始数放在右上角，往左和下搜，停止条件设置正确就行。代码如下：

public class Searcha2DMatrixII
{

  public static void main(String[] args)
  {
    /**
     * 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 = [[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]], target = 5
     * Output: true
     * Example 2:
     * 
     * 
     * Input: matrix = [[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]], target = 20
     * Output: false
     * 
     * 
     * 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
     */
    int[][] matrix = { { 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 } };
    System.out.println(searchMatrix(matrix, 5));
    System.out.println(searchMatrix(matrix, 20));
  }

  public static boolean searchMatrix(int[][] matrix, int target)
  {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
    {
      return false;
    }
    int m = matrix.length, n = matrix[0].length;
    if (target < matrix[0][0] || target > matrix[m - 1][n - 1])
    {
      return false;
    }
    int x = m - 1, y = 0;
    while (x >= 0 && y < n)
    {
      if (matrix[x][y] > target)
      {
        x--;
      }
      else if (matrix[x][y] < target)
      {
        y++;
      }
      else
      {
        return true;
      }
    }
    return false;
  }

}