文档章节

leetcode240 搜索二维矩阵 II

o
 osc_n6euf5h6
发布于 2019/03/20 00:52
字数 695
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目:

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例:

现有矩阵 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] ] 给定 target = 5,返回 true。 给定 target = 20,返回 false。


思路:

二分法。

  1. 先获取当前矩阵的最大值和最小值,即左上角的值和右下角的值 为(x1,y1)和(x2,y2)。当x1 = x2 且 y1 = y2时,说明矩阵为一个点。
  2. 求mid值,即 ( (x1+x2)/2 , (y1+y2)/2 )
  3. 将mid值与target进行比较,来决定接下来取查询那些范围 · 如果target = mid 说明找到了目标值 · 如果target < mid,说明以mid为最小值的那块矩阵,不会有target, target在其他范围 · 如果target > mid,说明以mid为最大值的那块矩阵里,不会有target, target在其他范围里面
  4. 接下来对其他范围进行递归查询

代码:

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

    //方法
    private boolean searchMatrix(int[][] matrix, int target, int x1, int y1, int x2, int y2) {
        if(x2 < x1 || y2 < y1){
            return false;
        }
        if(target < matrix[x1][y1] || target > matrix[x2][y2]){//若果小于矩阵最小值,或者大于矩阵最大值,直接返回false。
            return false;
        }
        int mid_x = (x1 + x2) / 2;
        int mid_y = (y1 + y2) / 2;

        if(target == matrix[mid_x][mid_y]){
            return true;
        }
        if(target < matrix[mid_x][mid_y]){ //target不在第四象限
            return (
            //查找第二象限
            searchMatrix(matrix,target,x1,y1,mid_x-1,mid_y-1) ||
            //查找第一象限
            searchMatrix(matrix,target,x1,mid_y,mid_x-1,y2) ||
            //查找第三象限
            searchMatrix(matrix,target,mid_x,y1,x2,mid_y-1)
            );
        }else { //target不在第二象限
            return (
            //查找第四象限
            searchMatrix(matrix, target,mid_x+1,mid_y+1,x2,y2) ||
            //查找第一象限
            searchMatrix(matrix,target,x1,mid_y+1,mid_x,y2) ||
            //查找第三象限
            searchMatrix(matrix,target,mid_x+1,y1,x2,mid_y)
            );
        }
    }
}  

但是我看其他人提交的代码,思路是从左下 或者 右上开始遍历。 思路是:

从左下角角标开始查找 如果>target 则向上移动角标 如果<target 则向右移动角标 如果==target 则返回True 如果角标出界还没找到target 则返回False

但是我认为这种不是最优的,比如二维数组只有一行或者一列的话,这就是一次时间复杂度为O(n)的遍历。

代码如下(代码是从右上角开始的)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target){
        if (matrix.length==0)
            return false;
        int i = matrix.length-1,j=0;
        while(i>=0 && j<matrix[0].length){
            if (matrix[i][j] == target)
                return true;
            else if(matrix[i][j]>target)
                i--;
            else if(matrix[i][j]<target)
                j++;
        }
        return false;
    }
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
leetcode240——搜索二维矩阵(medium)

一、题目描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例: 现有矩阵 matr...

404found
05/09
0
0
刷题建议

课程安排 知识点 题目+1 题目+2 日期 线性数据结构 - 数组 15.三数之和 560. 和为K的子数组 11. 盛最多水的容器 排序算法 179. 最大数 75. 颜色分类 1054. 距离相等的条形码 扩展线性数据结构...

bonelee
03/28
0
0
LeetCode 240. 搜索二维矩阵 II (C#实现)——二分查找,分治法

问题:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/ 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 示例: 现有矩阵 matrix 如下:...

osc_n6euf5h6
2019/03/19
2
0
精选 TOP 面试题

1 两数之和 46.5%简单2 两数相加 35.5%中等3 无重复字符的最长子串 31.1%中等4 寻找两个有序数组的中位数 35.9%困难5 最长回文子串 26.9%中等7 整数反转 33.0%简单8 字符串转换整数 (atoi) 1...

osc_5v9u1t19
2019/08/31
2
0
校招的常考算法类型以及对应的典型题目

数学 尾部的零 斐波纳契数列 x的平方根 x的平方根2 大整数乘法 骰子求和 最多有多少个点在一条直线上 超级丑数 比特位操作 将整数A转换为B 更新二进制位 二进制表示 O(1)时间检测2的幂次 二进...

osc_8wtzom6p
2018/01/09
2
0

没有更多内容

加载失败,请刷新页面

加载更多

Hacker News 简讯 2020-07-11

更新时间: 2020-07-11 00:00 Scientists make precise edits to mitochondrial DNA for first time - (nature.com) 科学家首次对线粒体DNA进行精确编辑 得分:66 | 评论:4 LibreOffice: The N......

FalconChen
46分钟前
95
0
是否有可能从另一个git存储库中挑选一个提交? - Is it possible to cherry-pick a commit from another git repository?

问题: I'm working with a git repository that needs a commit from another git repository that knows nothing of the first. 我正在使用一个git存储库,需要从另一个不知道第一个存储库......

技术盛宴
昨天
26
0
【LeetCode】53 盛最多水的容器

题目 解题思路 双指针法: https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/ 代码 public class Solution { ......

JaneRoad
昨天
20
0
阿里云OSS配置CDN加速

首先购买CDN流量包 然后添加域名 添加好后 然后将域名OSS.xxxx.com 解析到 生成的CDN域名上 这样就完成了

可达鸭眉头一皱
昨天
16
0
js 整数与小数正则替换片段

说明 /(\d+)/g 整数 /(\d+\.\d+)rem/g 小数 /(\d+\.\d+|\d+)rem/g 其中 | 或 条件 例子 全局查找带 rem 单位的,替换成 px 单位 let text = text.replace(/(\d+\.\d+|\d+)rem/g, function(s......

DrChenXX
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部