74、搜索二维矩阵

leetcode

Created At : 2020-07-26 00:19

Count:310 Views 👀 :

Comment:

示例 1:
示例 2:

代码

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

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

示例 1:

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

示例 2:

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

代码

从左下或者右上开始搜索

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int i = 0;
        int j = matrix[0].length - 1;
        boolean res = false;
        while(!res){
            if (matrix[i][j] == target) {
                res = true;
            }else if (matrix[i][j] > target){
                if (j == 0){
                    break;
                }
                j--;
            }else {
                if (i == matrix.length - 1){
                    break;
                }
                i++;
            }
        }
        return res;
    }
}

二分查找，二维数组映射为一维数组

class Solution{
    public boolean searchMatrix(int[][] matrix,int target) {
        int m = matrix.length;
        if (m == 0) {
            return false;
        }
        int n = matrix[0].length;
        int left = 0;
        int right = m*n-1;
        int pivotIdx,pivotElement;
        while(left <= right) {
            pivotIdx = (left + right)/2;
            pivotElement = matrix[pivotIdx/n][pivotIdx % n];
            if (target == pivotElement) {
                return true;
            }else {
                if (target < pivotElement) {
                    right = pivotIdx - 1;
                } else {
                    left = pivotIdx + 1;
                }
            }
        }
        return false;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com