首页 > 剑指offer：面试题04. 二维数组中的查找

剑指offer：面试题04. 二维数组中的查找

题目：二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 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。

限制：

0 <= n <= 10000 <= m <= 1000

解题思路：

首先选取二维数组当中右上角的数字。

  • 如果该数字等于target，则查找过程结束；
  • 如果该数字大于target，则剔除这个数字的所在列（由于该列是递增顺序，这个数字是这一列里的最小的数字，这一列的数字都会比target大）；
  • 如果该数字小于target，则剔除这个数字的所在行（同理，这个数字是这一行里最大的数字，所以这一行的数字都要比target小）；
  • 再次选取剩余区域的右上角的数字，然后重复上述的过程。

时间复杂度O(m+n)(其中 m 和 n 分别代表行数和列数)，空间复杂度O(1)

class Solution {
public:bool findNumberIn2DArray(vector>& matrix, auto target) {auto rows = matrix.size();auto columns = matrix[0].size();if(rows>0 && columns>0){    auto row = 0 ;auto column = columns-1;while(row=0){if(matrix[row][column]==target) {return true;}else if(matrix[row][column]>target) {column--;}else row++;}}return false;}
};

LeetCode代码提交报错：

reference binding to null pointer of type 'struct value_type'

后来找到问题是，测试用例如果直接给出一个空字符串的话，也就是说函数传进的是一个空的vector容器，那么在调用matrix[0]的时候就会下标越界，因为matrix[0]是不存在的。加上如下判断条件之后，顺利通过。

if(matrix.empty())  //不加这个传入为空的判断的话会访问越界return false;
class Solution {
public:bool findNumberIn2DArray(vector>& matrix, auto target) {if(matrix.empty())  //不加这个传入为空的判断的话会访问越界return false;auto rows = matrix.size();auto columns = matrix[0].size();if(rows>0 && columns>0){    auto row = 0 ;auto column = columns-1;while(row=0){if(matrix[row][column]==target) {return true;}else if(matrix[row][column]>target) {column--;}else row++;}}return false;}
};

 

更多相关：

  • valgrind 使用 kcachegrind 查看函数运行时间

    安装 首先安装运行分析函数时间的工具 kcachegrind 下载安装包 http://kcachegrind.sourceforge.net/，下载最新的 tar.gz 文件 解压文件，进入解压之后的目录，从 README 中可以找到安装方式，这里记录一下 cmake . make -j8 sudo make install...

  • Linux ISCSI配置

    一、简介 iSCSI（internet SCSI）技术由IBM公司研究开发，是一个供硬件设备使用的、可以在IP协议的上层运行的SCSI指令集，这种指令集合可以实现在IP网络上运行SCSI协议，使其能够在诸如高速千兆以太网上进行路由选择。iSCSI技术是一种新储存技术，该技术是将现有SCSI接口与以太网络(Ethernet)技术结合，使...

  • 记录CSS3 target伪类简介

    CSS3 target伪类是众多实用的CSS3特性中的一个。它用来匹配文档(页面)的URI中某个标志符的目标元素。具体来说，URI中的标志符通常会包含一个”#”字符，然后后面带有一个标志符名称，比如#respond，target就是用来匹配ID为respond的元素的。 现在在页面中，点击一个ID链接后，页面只会跳转到相应的位置，但...

  • flash玩转cookie

    经常有遇到说浏览器与flash之间不好debug,数据不好交流，确实每次遇到都得多写些代码。麻烦！ 这回我打算写个flash类，专门用来解决这些问题。这几天，我就先从cookie的读写开始，写了个cookie类，有了这个类，以后我就能直接在flash里面操作cookie了。一劳永逸，大伙如果觉得有用就拿去吧。我已经放在了google...

  • 剑指offer： 面试题03. 数组中重复的数字

    题目：找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1： 输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 限制： 2 <= n...

  • 【力扣网练习题】罗马数字转整数

      罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符          数值 I             1 V             5 X             10 L             50 C             100 D             500 M            ...

  • 杭电1716

    排列2 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2076    Accepted Submission(s): 816 Problem Description Ray又...

  • word中插入下标

    Word2007中为数字加上下标的几种方法： 一：通过插入>公式>>选择，通过此上下标。 二：写下数字，例如5，然后按ctrl+shift+=号三个键，就可添加上标，按ctrl+=号两键，就可标注下标。 三、开始菜单中的X2，X2 转载于:https://www.cnblogs.com/jufu/archive/2012/03/3...

  • 设置VSCode自动保存

     文件→自动保存（auto save）...

©2024 11GX.COM