LeetCode74二分搜索优化：二维矩阵中的高效查找策略

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

LeetCode74二分搜索优化：二维矩阵中的高效查找策略-LMLPHP

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

示例 2：

LeetCode74二分搜索优化：二维矩阵中的高效查找策略-LMLPHP

输入：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
-104 <= matrix[i][j], target <= 104

以右上或左下为起点进行搜索

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {

           int row =  matrix.length;
           int col =  matrix[0].length;

           int i = 0;
           int j = col-1;

           while(i>-1 && i<row && j>-1 && j<col){
                 

                 if(matrix[i][j] < target){
                        i++;
                 }else if(matrix[i][j] > target){
                        j--;
                 }else{
                     return true;
                 }
           }

           return false;

    }
}

这种解法效率不高需要用二分来优化，这道题目描述的矩阵具有两个关键属性：

由于这两个属性，虽然矩阵是二维的，但它可以被视为一个一维的有序数组。具体来说，如果我们将这个矩阵“展开”成一个一维数组，这个数组将是有序的。这使得我们可以在这个虚拟的一维数组上应用二分查找算法。

class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;

        int left = 0;
        int right = row * col - 1;

        while (left <= right) {
            int midIndex = left + (right - left) / 2;
            int midValue = matrix[midIndex / col][midIndex % col];

            if (midValue == target) {
                return true;
            } else if (midValue < target) {
                left = midIndex + 1;
            } else {
                right = midIndex - 1;
            }
        }

        return false;
    }
}

LeetCode1095.之山脉数组中查找目标值（相关话题：多重二分）-CSDN博客

击水三千里

LeetCode74二分搜索优化：二维矩阵中的高效查找策略

题目描述

相关文章