74. 搜索二维矩阵 I

题目描述:

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

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

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

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

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

解法一: O(m+n), S(1)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (target > matrix[i][j]) {
                i++;
            } else if (target < matrix[i][j]) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
}

解法二: O(log(m*n)), S(1) 二分法

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        int n = matrix.length, m = matrix[0].length;
        int low = 0, high = n * m - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // 从一维坐标转换至二维坐标
            int x = mid / m;
            int y = mid % m;
            if (target > matrix[x][y]) {
                low = mid + 1;
            } else if (target < matrix[x][y]) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

题目分析:

(1)这道题和搜索二维矩阵 II 很相似, 从右上角开始遍历, 如果target小于当前matrix[i][j], 排除本列, 如果大于, 排除本行.

(2)因为所有的都是升序, 所以我们用一维做二分, 转换成二维坐标即可. 总元素: NM个, 所以时间复杂度O(log(nm))