剑指offer 01. 二维数组中的查找
共 2825字,需浏览 6分钟
·
2021-06-12 21:34
前言
牛客网剑指 offer 的 66 道题,基本属于必刷题,帅地打算把 66 道的题解大致过一遍,大家也可以跟着帅地,每日一道刷起来!每道题会提供简单的思路以及测试通过的代码。
问题描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[
]
给定 target = 7,返回 true。
给定 target = 3,返回 false。
示例1
输入:7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值:true
说明:存在7,返回true
示例2
输入:3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值:false
说明:不存在3,返回false
题目链接:https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13
解答思路
一种简单的方法就是整个数组都遍历,当然,数组从左到右,从上到下都是有序的,如果你遍历整个数组的话,那就浪费了数组的局部有序性了。
如果我们从 row = 0 和col = 0开始遍历的话,发现右边的数比 array[row] [col] 大,而下边也比 array[row] [col]大,这样的话,貌似局部有序性没有派上用场
遍历不一定就一定要从 row = 0 和 col = 0开始,有时候,换个角度,一切就豁然开朗了。
实际上我们从数组的左下角开始遍历的话
1、如果array[row] [col] > target,那么 target 必定在元素 array[row] [col] 所在列的上边,则往上移动。
2、如果 array[row] [col] < target,那么target必定在元素 array[row] [col] 所在行的右边,则往右移动。
3、否则找到目的数。
这样,就完美利用到局部有序性了。代码如下:
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null)return false;
int row = array.length - 1;
int col = array[0].length - 1;
int j = 0;
while (row >= 0 && j <= col) {
if (array[row][j] > target) {
row--;
} else if (array[row][j] < target) {
j++;
} else {
return true;
}
}
return false;
}
}
此种方法对时间复杂度是O(m + n),(m和n表示数组的长度和宽度)
当然,这里还有另外一种方法,因为每一行都是有序的,就是对每一行进行二分查找,这种方法的话,时间复杂度是 O(nlogm),这种方法就不提供代码了。
另外,所有题解及其代码,都会同步到帅地的个人网站,这样阅读起来会舒服一些,方便大家学习,链接:https://www.iamshuaidi.com/1343.html
PS:点击阅读原文即可直达,推荐 PC 端打开。