Leetcode-074-搜索二维矩阵

Leetcode-074-搜索二维矩阵

题目描述

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

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

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

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

算法思路

思路

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

• 我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，

• 然后在该元素所在行中二分查找目标值是否存在。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = searchColumn(matrix,target);             // 搜索在哪一行
        if(rowIndex < 0){
            return false;                                       
        }
        return searchRow(matrix[rowIndex],target);              // 找到所在行号后，再在行内进行搜索
    }

    // 第一次二分：搜索target在哪一行
    public int searchColumn(int[][] matrix, int target){
        int low  = 0;
        int high = matrix.length - 1;
        while(low < high){
            int mid = (high + low + 1) >>> 1;                    // + 1：目的是为了防止死循环的发生（left = mid 这种情况都需要+1）
            if(matrix[mid][0] <= target){                        // 比较每一行第一个元素与target 判断在哪一行
                low = mid;                                       // 下一轮搜索的区间是 [mid, high]
            }else{
                high = mid - 1;                                  // 下一轮搜索的区间是 [low, mid]
            }
        }
        return low;
    }

    // 第二次二分：确定行号后进行行内查找
    public boolean searchRow(int[] row,int target){
        int low  = 0;
        int high = row.length - 1;
        while(low < high){
            int mid = (low + high) >>> 1;
            if(row[mid] < target){                              // 小于 target 的元素一定不是解      
                low = mid + 1;                                  // 下一轮搜索的区间是 [mid + 1, high]
            }else{
                high = mid;                                     // 下一轮搜索的区间是 [low, mid]
            }
        }
        // 确认一下结果是否正确
        if(row[low] == target){
            return true;
        }
        return false;
    }
}

复杂度分析

• 时间复杂度 ： O（logm） + O(logn) = O(logmn)
• 空间复杂度 ： O(1)

打赏