Search a 2D Matrix II

更新时间：2022-05-09 04:00:58

搜索2维数组；如果数组中存在目标值，返回true，否则返回false

Write an efficient algorithm that searches for a value in an m x n matrix. This 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.

For example,

Consider the following 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]
]

Given target = 5, return true.

Given target = 20, return false.

遍历的话肯定效率低下。设立游标移动搜索。那么问题是从哪里开始搜索？

比较好的办法是从右上角开始。如果右上角的数字大于target，那么这一列没有target；向左一列移动

如果小于target，那么这一行没有target，向下一行移动

搜索停止的条件就是越界

Java代码：

 1 package com.rust.cal;
 2 
 3 public class Searcha2DMatrixII {
 4 
 5     public static boolean searchMatrix(int[][] matrix, int target) {
 6         if (matrix.length == 0 || matrix[0].length == 0) {
 7             return false;
 8         }
 9         int dy = matrix[0].length - 1;
10         int delta = matrix[0][dy];
11         int dx = 0;
12         while(dx < matrix.length && dy >= 0){
13             if (matrix[dx][dy] == target) {
14                 return true;
15             } else if (matrix[dx][dy] < target) {
16                 dx++;
17             } else {
18                 dy--;
19             }
20         }
21         return false;
22     }
23     public static void main(String args[]){
24         int matrix[][] = {
25                 {1 ,2 ,3 ,4 ,9 },
26                 {6 ,7 ,8 ,10,19},
27                 {17,18,30,31,32}
28         };
29         
30         int matrix1[][] = {
31                 {1,2},
32                 {4,5},
33                 {6,17},
34                 {10,20}
35         };
36         
37         int matrix2[][] = {
38                 {1,3,5,7,9,13,17},
39                 {2,4,6,8,10,16,20}
40         };
41         
42         System.out.println("matrix has 17?  " + searchMatrix(matrix, 17));
43         System.out.println("matrix has 18?  " + searchMatrix(matrix, 18));
44         System.out.println("matrix has 19?  " + searchMatrix(matrix, 19));
45         System.out.println("matrix1 has 4?  " + searchMatrix(matrix1, 4));
46         System.out.println("matrix2 has 4?  " + searchMatrix(matrix2, 4));
47         
48     }
49 }

输出：

matrix has 17?  true
matrix has 18?  true
matrix has 19?  true
matrix1 has 4?  true
matrix2 has 4?  true

上一篇 : ：AddBinary下一篇 : Divide Two Integers

Search a 2D Matrix II

相关阅读

推荐文章