本文共 1180 字，大约阅读时间需要 3 分钟。

为了高效地判断m×n矩阵中是否存在目标值，我们可以利用矩阵的特殊性质：每行有序递增，且每行的第一个数大于上一行的最后一个数。这种结构使得我们可以通过逐行查找和二分查找来优化搜索过程。

方法思路

这种方法充分利用了每行有序的特性，减少了不必要的比较，提高了效率。

解决代码

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    if (m == 0) return false;
    int n = matrix[0].length;
    for (int i = 0; i < m; i++) {
        int[] row = matrix[i];
        if (row[0] > target) {
            continue;
        }
        if (row[n - 1] < target) {
            continue;
        }
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
}

代码解释

• 遍历每一行：使用一个循环遍历矩阵的每一行。
• 剪枝处理：对于每一行，首先检查该行的第一个数是否大于目标值或最后一个数是否小于目标值。如果是，则跳过该行。
• 二分查找：在可能包含目标值的行中，使用二分查找来确定是否存在目标值。如果找到目标值，返回true；否则继续下一行。
• 返回结果：如果遍历完所有行后都没有找到目标值，返回false。

这种方法的时间复杂度为O(m log n)，能够高效地处理较大的矩阵。

转载地址：http://tamq.baihongyu.com/