提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode No.74 搜索二维矩阵（二分查找）

2023-03-20 14:55:22 时间

一、题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false

提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -10^4 <= matrix[i][j], target <= 10^4

二、解题思路

由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。

三、代码

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n=matrix.length;
        int m=matrix[0].length;
        int row=binarySearchRow(matrix,target);
        if(row==-1){
            return false;
        }
        int column=binarySearchColumn(matrix[row],target);
        if(column==-1){
            return false;
        }
        return true;
    }
    int binarySearchRow(int[][] matrix, int target){
        int low=0,high=matrix.length-1;
        while(low<=high){
            if(low==high){
                return low;
            }
            int mid=(high+low)/2;
            if(matrix[mid][0]<=target && matrix[mid+1][0]>target){
                return mid;
            }
            if(matrix[mid][0]<target){
                low=mid+1;
            }
            if(matrix[mid][0]>target){
                high=mid-1;
            }
        }
        return -1;
    }
    int binarySearchColumn(int[] array, int target){
        int low=0,high=array.length-1;
        while(low<=high){
            int mid=(high+low)/2;
            if(array[mid]==target){
                return mid;
            }
            if(array[mid]<target){
                low=mid+1;
            }
            if(array[mid]>target){
                high=mid-1;
            }
        }
        return -1;
    }

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

四、复杂度分析

时间复杂度：O(logm+logn)=O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。

空间复杂度：O(1)。

相关文章