[leetcode-查找]--74. Search a 2D Matrix

向右看齐 2022-07-12 03:01 135阅读 0赞

Question 74. Search a 2D Matrix

> Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
> 
> (1) Integers in each row are sorted from left to right.  
> (2)The first integer of each row is greater than the last integer of the previous row.
> 
> For example,  
> Consider the following matrix:  
> \[  
> \[1, 3, 5, 7\],  
> \[10, 11, 16, 20\],  
> \[23, 30, 34, 50\]  
> \]  
> Given target = 3, return true.
> 
> 中文：对于一个整型二维数组，每一行都是升序有序的，下一行第一个数比上一行最后一个数大。 对于一个给定的目标数target 判断是否在二维数组中，若在返回true，不在返回false。

实现： 这里我首先遍历每一行的第一个数据，获取到target应该在哪一行进行检验。然后在对应的行使用二分查找，找到数据。对于m\*n 的数组，时间复杂度是O(m\*logn)。

实现源码：

/** * 先找列, 遍历. 找行用二分查找 * @param matrix * @param target * @return */
    public static boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length==0 || matrix[0].length==0){
            return false;
        }
    
        int rows = matrix.length;//总行数
        int columns = matrix[0].length;//总列数
        int row=0;//比较的行数
        int i=0;
        //找到比较行
        for(i=0; i<rows; i++){
            if( (matrix[i][0] <= target) && (i < rows-1) && (matrix[i+1][0] > target)){
                row = i;
                break;
            }
            if( (matrix[i][0] <= target) && ( i == rows-1)){
                row = i;
                break;
            }
        }
    
        //二分查找找到对应的位置,找不到返回false
        int lo=0, hi=matrix[row].length-1;
        int mid;//中间索引
    
        while (lo <= hi){
            mid = (lo+hi)/2;
    
            if(matrix[row][mid] == target){
                return true;
            } else if(matrix[row][mid] < target){
                lo = mid+1;
            }else{
                hi = mid-1;
            }
        }
        return false;
    }

本文完整代码 github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question74.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question74.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question74.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question74.java