题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例1

输入：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
输出：true

题目分析

二分查找

每一行二分查找一次
时间复杂度 O(m * log n)

贪心

从左上角开始查找，会发现要同时面临向右和向下两个选择。
但如果把右上角作为初始点，每次移动就只存在一个选择：
– 如果比 target 小，则向下走
– 如果比 target 大，则向左走

因此从右上角开始枚举即可，时间复杂度 O(m + n)
当然，从左下角开始枚举也是可以的。

Java

public boolean searchMatrix1(int[][] matrix, int target) {
    for (int[] row : matrix) {
        if (Arrays.binarySearch(row, target) >= 0) {
            return true;
        }
    }
    return false;
}

public boolean searchMatrix2(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] > target) {
            j--;
        } else if (matrix[i][j] < target) {
            i++;
        } else {
            return true;
        }
    }
    return false;
}

Kotlin

fun searchMatrix1(matrix: Array<IntArray>, target: Int): Boolean {
    for (row in matrix) {
        if (row.binarySearch(target) >= 0) {
            return true
        }
    }
    return false
}

fun searchMatrix2(matrix: Array<IntArray>, target: Int): Boolean {
    val m = matrix.size
    val n = matrix[0].size
    var i = 0
    var j = n - 1
    while (i < m && j >= 0) {
        if (matrix[i][j] > target) {
            j--
        } else if (matrix[i][j] < target) {
            i++
        } else {
            return true
        }
    }

    return false
}