leetcode—搜索二维矩阵II-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode—搜索二维矩阵II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

示例 1：

leetcode—搜索二维矩阵II,leetcode,矩阵,算法,java

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

方法一

暴力求解

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 方法一 ：暴力求解
        // 遍历数组
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == target){
                    return true;
                }
            }
        }
        // 若遍历完数组还是没有找到目标值 返回false
        return false;

    }
}

方法二

对矩阵的每一行采用二分查找进行查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 遍历矩阵的第一层 即每一行 使用增强for循环
        for(int[] row: matrix){
            int index = binarySearch(row, target);
            if(index >= 0){
                return true;
            }
        }
        return false;

    }
    // 二分查找
    public int binarySearch(int[] matrix, int target){
        int left = 0;
        int right = matrix.length -1;
        while(left <= right){
            int mid = (left + right)/2;
            if(matrix[mid] == target){
                return mid;
            }else if(matrix[mid] > target){
                right = mid -1;
            }else{
               left = mid + 1; 
            }
        }
        // 若还未找到 返回-1
        return -1;
    }
}

方法三

Z字型查找

从矩阵的右上角（0，n-1）进行搜索

具体过程. - 力扣（LeetCode）文章来源地址https://www.toymoban.com/news/detail-796615.html

若matrix[x,y] == target,返回true
若 matrix[x,y] > target, 那么第y 列的所有元素都是大于target的因此 y--
若matrix[x,y] < target, 那么第 x 行的所有元素都小于target，因此x++

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 数组判空
        if(matrix.length == 0){
            return false;
        }
        int m = matrix.length;  // 计算矩阵的行数
        int n = matrix[0].length;   // 计算矩阵的列数
        // 从右上角开始查找
        int x = 0;
        int y = n-1;

        // 循环查找
        while(x < m && y >= 0){
            if(matrix[x][y] == target){
                return true;
            }else if(matrix[x][y] > target){
                // 消去列
                y--;
            }else{
                // 消去行
                x++;
            }
        }
        // 若循环结束 还未找到 返回false
        return false;

    }
}

到了这里，关于leetcode—搜索二维矩阵II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！