关于java:LeetCode074搜索二维矩阵

40次阅读

共计 1042 个字符，预计需要花费 3 分钟才能阅读完成。

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

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最初一个整数。

示例阐明请见 LeetCode 官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：二分查找法

因为 matrix 数组的行和列都是有序的，所以采纳二分查找法是比拟高效的办法，具体查找的过程如下：

首先，从 matrix 数组的左下角开始查找，即初始索引位 i 为 matrix.length - 1，j 为 0；

如果以后地位的值等于 target，则间接返回 true；

如果以后地位的值小于 target，则地位右移，即 j 加一；

如果以后未知的值大于 target，则地位上移，即 i 减一；

查找完结的条件是 i 不小于 0 且 j 不大于 matrix[0].length - 1，即查找的值不能超过 matrix 数组的界线。

如果查找完结都没有找到和 target 相等的值，则返回 false。

public class LeetCode_074 {public static boolean searchMatrix(int[][] matrix, int target) {
        // 从 matrix 数组的左下角开始查找
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j <= matrix[0].length - 1) {if (matrix[i][j] == target) {
                // 如果以后地位的值等于 target，间接返回 true
                return true;
            } else if (matrix[i][j] < target) {
                // 如果以后地位的值小于 target，右移
                j++;
            } else if (matrix[i][j] > target) {
                // 如果以后未知的值大于 target，上移
                i--;
            }
        }
        // 如果查找完结都没有找到和 target 相等的值，则返回 false
        return false;
    }

    public static void main(String[] args) {int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(searchMatrix(matrix, 13));
    }
}