算法 查找 【剑指 Offer 04 二维数组中的查找】
2021/4/22 22:26:31
本文主要是介绍算法 查找 【剑指 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 <= 1000
0 <= m <= 1000
二、思路
最简单的思路肯定是一一遍历。但是这样的时间复杂度很高,我们需要设计一个更高效的算法,所以需要先研究该二维数组:
题目中有这样一句话:每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
也就是说,右上角的元素是第一行元素中最大的,同时是最后一列元素中最小的。
右上角元素的左边第一个元素是第一行元素中次大的,同时是倒数第二列元素中最小的。
整理可得:第一行第m列元素是第一行第m大的,同时是第m列中最小的。
那么我们可以拿目标和第一行最后一列的元素进行比较,比较顺序为从右至左。
举个例子:
假如我们要找8,8比15小,说明8所在的列在15所在列的左侧,那么接下来和11比;
8比11小,说明8所在的列在11所在列的左侧,那么接下来和7比;
8比7大,证明如果矩阵中存在8,那么8肯定与7同列,且在7的下方。那么接下来将行增加一行,进行比较;
最终找到了8。
那么对于找不到的元素呢?
我们可以设置一个循环,假设一开始就找不到,设置一个flag = 0;如果找到了就设置flag = 1,然后跳出循环;
如果还是找不到,那么需要一个结束循环的条件:行超过了最大行,或者列为负数。
三、代码
class Solution { public: bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) { bool found = false; //如果数组为空,肯定找不到 //一共matrix.size()行 //matrix[0].size()列 if (matrix.empty()) { return found; } //最大行 int rows = matrix.size(); //最大列 int columns = matrix[0].size(); //当前元素从右上角开始 //当前行设置为0 int row = 0; //当前列设置为列的边界,因为数组下标从0开始,所以边界为最大列-1 int column = columns-1; //循环条件:行没有超过最大行,列没有为负数 while (row < rows && column >= 0) { //如果找到目标,即返回 if (target == matrix[row][column]) { found = true; break; } //如果目标比当前元素小,而当前元素又是该列中最小的,所以往左缩短一列 else if (target < matrix[row][column]) { column--; } //如果在目标元素已经小于右边所有元素的情况下,目标元素又比当前元素大,说明目标元素在当前元素下方,所以往下增加一列 else { row++; } } return found; } };
这篇关于算法 查找 【剑指 Offer 04 二维数组中的查找】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?