leetcode—搜索二维矩阵II

发布时间:2024年01月17日

编写一个高效的算法来搜索?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

方法一

暴力求解

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)

  • 若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;

    }
}

文章来源:https://blog.csdn.net/m0_67281369/article/details/135605160
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。