LeetCode74-搜索二维矩阵

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/search-a-2d-matrix/

中文链接：https://leetcode-cn.com/problems/search-a-2d-matrix/

题目详述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

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

示例 2:

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

题目详解

  • 根据该矩阵的特性，从整体上看，矩阵的左上方到右下方是增大的。
  • 可以以矩阵的副对角线为基准进行查找（从左下角到右上角或从右上角到左下角）。
  • 这里从左下角开始，若矩阵中的元素 matrix[i][j] < target，说明 target 可能存在于该元素所在行的右侧，进行 ++j 操作。
  • 若矩阵中的元素 matrix[i][j] > target，说明 target 可能存在于该元素上方的行中，进行 --i 操作。
  • 若相等则说明存在矩阵中存在 target 返回 true。
  • 若整个过程结束仍未找到说明矩阵中不存在 target 返回 false。
  • 时间复杂度为 O(m + n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00074 {

    public boolean searchMatrix(int[][] matrix, int target) {
        int i = matrix.length - 1;
        int j = 0;
        while (i >= 0 && j < matrix[0].length) {
            if (matrix[i][j] < target) {
                ++j;
            } else if (matrix[i][j] > target) {
                --i;
            } else {
                return true;
            }
        }
        return false;
    }
}
  • 因为二维矩阵每行中的整数从左到右按升序排列，并且每行的第一个整数大于前一行的最后一个整数，可以把矩阵看成是一个由小到大排序的一维数组。
  • ”数组 + 有序“可以联想到二分查找。
  • 从一维还原到二维过程中，中间的那个数的下标从一维的 mid 转换为二维的 (mid / n, mid % n)，其中 n 为每一行的元素个数。
  • 时间复杂度为 O(log(m*n))。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class LeetCode_00074 {

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int lo = 0;
        int hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int val = matrix[mid / n][mid % n];
            if (val < target) {
                lo = mid + 1;
            } else if (val > target) {
                hi = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

二分写法的更好一种方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00074 {

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l < r) {
            int mid = l + r >>> 1;
            if (matrix[mid / n][mid % n] >= target) r = mid;
            else l = mid + 1;
        }
        return matrix[r / n][r % n] == target;
    }
}