LeetCode 74 & 240 Search a 2D Matrix I,II

74. Search a 2D Matrix

74. Search a 2D Matrix
            DescriptionHintsSubmissionsDiscussSolution
    Pick One
    Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

    Integers in each row are sorted from left to right.
    The first integer of each row is greater than the last integer of the previous row.
    Example 1:

    Input:
    matrix = [
            [1,   3,  5,  7],
            [10, 11, 16, 20],
            [23, 30, 34, 50]
            ]
    target = 3
    Output: true
    Example 2:

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

一个矩阵,每一行都是递增顺序,并且下一列比上一列的最大值要大。给定一个目标值,判断这个target是否在这个矩阵中。

同样的给出两种解法

解法一:

从第一列中采用二分搜索找到合适的行,再在这一行中采用二分搜索法找到合适的列即可

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
    if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
    int row = searchMatrix_BS1_hepler(matrix,0,matrix.length-1,target);
    return searchMatrix_BS2_helper(matrix,0,matrix[0].length-1,target,row);
}

public boolean searchMatrix_BS2_helper(int[][] matrix,int left,int right,int target,int row){
    int mid = (right -left)/2 + left;
    if (left>right) return false;
    if (target == matrix[row][mid]) return true;
    if (target>matrix[row][mid]) {
        left = mid+1;
        return searchMatrix_BS2_helper(matrix,left,right,target,row);
    } else {
        right = mid-1;
        return searchMatrix_BS2_helper(matrix,left,right,target,row);
    }
}

public int searchMatrix_BS1_hepler(int[][] matrix,int left,int right,int target){
    int mid = (right -left)/2 + left;
    if (target == matrix[mid][0]){
        return mid;
    }else if (target>matrix[mid][0]){
        if (target <= matrix[mid][matrix[0].length-1]){
            return mid;
        } else {
            left = mid+1;
            return searchMatrix_BS1_hepler(matrix,left,right,target);
        }
    }else if (target<matrix[mid][0]){
        if (target >=matrix[mid-1][0]){
            return mid-1;
        }else {
            right = mid -1;
            return searchMatrix_BS1_hepler(matrix,left,right,target);
        }
    }
    return -1;
}

这种方法不是直接的,就当做是练习一下在矩阵中使用二分查找法了。

解法二:

更加直接的解法,其实这就是一个一维有序的数组分为几段后变成了二维数组,所以就采用一维数组的二分查找法就可以很容易的写出本题目的solution。

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
    if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
    return searchMatrix_helper(matrix,target,0,matrix.length*matrix[0].length-1);
}

public boolean searchMatrix_helper(int[][] matrix, int target,int left,int right){
    if (left > right ) return false;
    int mid = (right -left)/2+left;
    int row = mid/matrix[0].length;
    int col = mid - matrix[0].length*row;
    if (target == matrix[row][col]) return true;
    if (target>matrix[row][col]) return searchMatrix_helper(matrix,target,mid+1,right);
    else return searchMatrix_helper(matrix,target,left,mid-1);
}

240.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

题目大意:一个矩阵,从左到右,从上到下,都是递增的顺序,给定一个目标值target,问在这个矩阵中能否找到这样的一个target。

观察矩阵可以发现,将这个target值与右上角的值相比较,如果target大于这个值,那么target若存在则绝对不可能在这一行的左边的数里面,同理可以知道,如果target小于这个值,那么target若存在则绝对不可能在这一列的下面的数里面。这样一步一步的最小目标区域即可,注意循环的退出条件,和递归的退出条件,都是放row或者col的值超出范围终止。

解法一:

递归解法:

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
        if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
        return searchMatrix(matrix,target,0,matrix[0].length-1);
    }
    
    public boolean searchMatrix(int[][] matrix, int target,int row ,int col){
        if (row>=matrix.length||col<0) return false;
        if (matrix[row][col] == target) return true;
       
        if (matrix[row][col] < target) {
            return searchMatrix(matrix,target,row+1,col);
        }else {
            return searchMatrix(matrix,target ,row,col-1);
        }
    }

解法二:

非递归解法:

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0||matrix[0].length==0) return false;
        int row = 0,col = matrix[0].length-1;
        while (row<matrix.length&&col>=0){
            if (matrix[row][col]>target){
                col--;
            }else if (matrix[row][col]<target){
                row++;
            }else {
                return true;
            }
        }
        return false;   
    }

总结:

矩阵中的查找法要充分利用矩阵的特征,将其转为我们熟知的查找法。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【编程之美】最短路径

最短路径 任意给定两个数字A和B,通过将A和6个数(7,-7,5,-5,12,-12)做加减运算,运算次数不限,每个数可以被使用多次,求从A到B最少要经过多少次...

4146
来自专栏计算机视觉与深度学习基础

Leetcode 78 Subsets

Given a set of distinct integers, nums, return all possible subsets. Note: The...

1996
来自专栏HansBug's Lab

3223: Tyvj 1729 文艺平衡树

3223: Tyvj 1729 文艺平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1347  Sol...

4035
来自专栏聊聊技术

原 初学算法 - 求凸包的Garham's

47810
来自专栏自学笔记

Data Structure_图图论带权图

交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

791
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

2606
来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

4668
来自专栏数据结构与算法

1003. 猜数游戏 (Standard IO)

题目描述 有一个“就是它”的猜数游戏,步骤如下:请你对任意输入的一个三位数x,在这三位数后重复一遍,得到一个六位数,467-->467467.把这个数连续除以7...

3698
来自专栏鸿的学习笔记

写给开发者的机器学习指南(十)

An attempt at rank prediction for topselling books using text regression

953
来自专栏数据结构与算法

BZOJ4766: 文艺计算姬

Description "奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺 术细胞。普通计算机能计算一个带...

3378

扫码关注云+社区

领取腾讯云代金券