leetcode-74-搜索二维矩阵

题目描述:

编写一个高效的算法来判断 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

要完成的函数:

bool searchMatrix(vector<vector<int>>& matrix, int target) 

说明:

1、这道题给定一个m行n列的矩阵,要求编写一个高效的算法来判断矩阵中是否含有target这个元素。

如果存在,返回true,否则返回false。

2、这道题其实就是二分法在矩阵上的应用,整个矩阵是升序的。

我们先用二分法确定target可能会在哪一行,接着再用二分法确定target在哪一列,或者不存在。

代码如下:(附详解)

    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        if(matrix.size()==0||matrix[0].size()==0)return false;//[]或者[[]]的边界条件
        int hang=matrix.size(),lie=matrix[0].size(),left=0,right=hang-1,med,t;
        while(left<=right)//二分法判断target在哪一行
        {
            med=(left+right)/2;
            if(target<matrix[med][0])
                right=med-1;
            else if(target>matrix[med][lie-1])
                left=med+1;
            else//找到元素在med这一行了
            {
                t=med;
                left=0;
                right=lie-1;
                while(left<=right)//用二分法找到target在哪一列
                {
                    med=(left+right)/2;
                    if(matrix[t][med]==target)//找到了返回true
                        return true;
                    else if(target<matrix[t][med])
                        right=med-1;
                    else
                        left=med+1;
                }
                return false;//target大于当前行最后一个元素或者小于第一个元素,返回false
            }
        }
        return false;//target小于矩阵的第一行第一个元素,或者大于矩阵最后一行最后一个元素,返回false
    }

上述代码实测8ms,beats 97.83% of cpp submissions。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏杂七杂八

numpy科学计算包的使用2

利用数组进行数据处理 NumPy数组使你可以将许多种数据处理任务表述为简洁的数组表达式(否则需要编写循环)。用数组表达式代替循环的做法,通常被称为矢量化。 矢...

37712
来自专栏机器学习算法与Python学习

Python: numpy总结(3)

21、dot矩阵点积 例子: ll = [[1,2,3],[4,5,6],[7,8,9]]ld = dot(ll,ll) print 'dot:',l...

3394
来自专栏chenjx85的技术专栏

leetcode-884-两句话中的不常见单词

给定两个句子 A 和 B 。 (句子是一串由空格分隔的单词。每个单词仅由小写字母组成。)

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

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

2286
来自专栏菜鸟程序员

【Java】随机数详解

2434
来自专栏Python攻城狮

科学计算工具Numpy1.ndarray的创建与数据类型2.ndarray的矩阵运算ndarray的索引与切片3.ndarray的元素处理元素判断函数元素去重排序函数4.2016年美国总统大选民意调查

Numpy:提供了一个在Python中做科学计算的基础库,重在数值计算,主要用于多维数组(矩阵)处理的库。用来存储和处理大型矩阵,比Python自身的嵌套列表结...

2703
来自专栏Petrichor的专栏

Tensor

  在 TensorFlow 中用 tensor 数据结构来代表所有的数据, 计算图中, 操作间传递的数据都是 tensor。

1502
来自专栏钟绍威的专栏

矩阵的基本知识构造重复矩阵的方法——repmat(xxx,xxx,xxx)构造器的构造方法单位数组的构造方法指定公差的等差数列指定项数的等差数列指定项数的lg等差数列sub2ind()从矩阵索引==》

要开始学Matlab了,不然就完不成任务了 java中有一句话叫作:万物皆对象 在matlab我想到一句话:万物皆矩阵 矩阵就是Java中的数组 ...

29510
来自专栏哈雷彗星撞地球

算法之路(二)呈现O(logN)型的三个算法典型时间复杂度

我们知道算法的执行效率,可以从它的时间复杂度来推算出一二。而典型的时间复杂度有哪些类型呢?

874
来自专栏木子昭的博客

机器学习三剑客之NumpyNumpy计算(重要)

NumPy是Python语言的一个扩充程序库。支持高级大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。Numpy内部解除了Python的PI...

3706

扫码关注云+社区

领取腾讯云代金券