[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 条评论
登录 后参与评论

相关文章

来自专栏机器学习与自然语言处理

04-树5. File Transfer--并查集

  对于一个集合常见的操作有:判断一个元素是否属于一个集合;合并两个集合等等。而并查集是处理一些不相交集合(Disjoint Sets)的合并及查询问题的有利工...

1865
来自专栏开源优测

[快学Python3]数据结构与算法-二分查找

概述 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好。 其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁...

2089
来自专栏大闲人柴毛毛

动态规划法(二)——弗洛伊德算法

问题描述 给定一个带权有向图,计算任意两结点间的最短路径。 迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉...

3787
来自专栏算法修养

HDU 5876 大连网络赛 Sparse Graph

Sparse Graph Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262...

3246
来自专栏HansBug's Lab

3377: [Usaco2004 Open]The Cow Lineup 奶牛序列

3377: [Usaco2004 Open]The Cow Lineup 奶牛序列 Time Limit: 10 Sec  Memory Limit: 128 ...

3177
来自专栏小樱的经验随笔

POJ 1659 Frogs' Neighborhood(可图性判定—Havel-Hakimi定理)【超详解】

Frogs' Neighborhood Time Limit: 5000MS Memory Limit: 10000K Total Submis...

2848
来自专栏小樱的经验随笔

从零开始学建树(树的分治,树的重心)

分治算法在树的路径问题中的应用 一、树的分治算法 树的分治算法是分治思想在树型结构上的体现。 任一个具有n个节点的连通路,它的任何一棵树的树枝数为n-1 分治:...

2514
来自专栏有趣的Python

9-玩转数据结构-线段树

上一章我们介绍了堆,这一章我们介绍一种新的树结构,线段树(区间树) Segment Tree

2354
来自专栏GIS讲堂

geotools中等值面的生成与OL3中的展示

本文讲述如何在geotools中IDW插值生成等值面,并根据给定shp进行裁剪,并生成geojson数据,以及Openlayers3中展示。

1235
来自专栏Bingo的深度学习杂货店

Q70 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time y...

3395

扫码关注云+社区