[LeetCode] 74. Search a 2D Matrix

【原题】

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.

For example,

Consider the following matrix:

[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]

Given target = 3, return true. 【解释】 给定一个二维数组每一行有序,行与行之间有序,给定一个target,要求返回该元素是否在二维数组中。 【思路】 有序自然想到二分查找。但这题需要使用两次二分查找,首先二分查找到行,然后在该行中再使用二分(刚开始,使用顺序查找得到行号也可以过)。假设二维矩阵为mxn,则算法的复杂度为O(logm+logn)O(logm+logn).

public class Solution {
//查找列
        public boolean binarySearchCol(int[][] matrix, int row, int target){
        int left=0,right=matrix[row].length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(matrix[row][mid]==target)
                return true;
            if(matrix[row][mid]>target)
                right=mid-1;
            else 
                left=mid+1;
        }
        return matrix[row][left]==target;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        if(m==0) return false;
        int n=matrix[0].length;
        if(n==0) return false;
        int left=0,right=m-1;
        /*注意这个二分查找要找到可能在的行,所以没有找到对应的target不能直接返回false,
        而要在最可能的一行单重继续查找*/
        while(left<right){
            int mid=(left+right+1)/2;
            if(matrix[mid][0]>target)
                right=mid-1;
            else if(matrix[mid][0]<target)
                left=mid;
            else return true;        
        }
       return  binarySearchCol(matrix, left,target);   
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏bboysoul

1494: C语言实验题――温度转换

描述:输入一个华氏温度,输出摄氏温度,其转换公式为:C=5(F-32)/9 输入:输入数据只有一个实数,即华氏温度。 输出:输出数据只有一个,即摄氏温度,保...

724
来自专栏王金龙的专栏

svg.js教程及使用手册详解(二)

上篇简要介绍了svg.js的基本信息和基本用法,这篇开始详细讲解svg.js的用法。

664
来自专栏desperate633

详解排序算法--堆排序选择排序堆排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩...

573
来自专栏bboysoul

1067: 成绩评估

描述:我们知道,高中会考是按等级来的。90~100为A; 80~89为B; 70~79为C; 60~69为D; 0~59为E。 编写一个程序,对输入的...

612
来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

1013
来自专栏PHP技术

PHP实现四种基本排序算法

许多人都说算法是程序的核心,算法的好坏决定了程序的质量。作为一个初级phper,虽然很少接触到算法方面的东西。但是对于基本的排序算法还是应该掌握的,它是程序开发...

34912
来自专栏来自地球男人的部落格

[LeetCode] 523. Continuous Subarray Sum

【原题】 Given a list of non-negative numbers and a target integer k, write a fun...

2078
来自专栏落影的专栏

Metal图像处理——颜色查找表(Color Lookup Table)

一张1024x1024的普通图片,是由1024 * 1024=1048576个像素点组成,每个像素点包括RGBA共32bit,常见的图像处理是对相邻像素点颜色、...

896
来自专栏Python专栏

浅尝Python快速排序

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

LOJ#6282. 数列分块入门 6

内存限制:256 MiB时间限制:500 ms标准输入输出 题目类型:传统评测方式:文本比较 上传者: hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

2427

扫码关注云+社区