Leetcode(74) Search a 2D Matrix

发表于 | 更新于 | 分类于

Description:

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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

解法：

搜索题，如果遍历整个矩阵一定是超时的，不过因为矩阵的排列存在大小规律，可以根据这一特点调整搜索策略，先根据大小关系定位目标可能在的行，然后再遍历该行查找目标。值得注意的是需要考虑边界条件。具体实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public boolean searchMatrix(int\[\]\[\] matrix, int target) {
        if (matrix.length == 0 || matrix\[0\].length == 0) {
            return false;
        }
        int resulti = 0;
        boolean result = false;
        for (int i = 0; i < matrix.length; i++) {
            if (target < matrix\[i\]\[0\]) {
                resulti = i - 1;
                result = true;
                break;
            } else if (target == matrix\[i\]\[0\]) {
                return true;
            }
            if (i == matrix.length - 1) {
                resulti = i;
                result = true;
            }
        }
        if (!result) {
            return result;
        }
        if (resulti == -1) {
            return false;
        }
        for (int j = 0; j < matrix\[resulti\].length; j++) {
            if (matrix\[resulti\]\[j\] == target) {
                return true;
            }
        }
        return false;
    }
}