剑指offer 01. 二维数组中的查找

苦逼的码农

共 2825字,需浏览 6分钟

 ·

2021-06-12 21:34

前言

牛客网剑指 offer 的 66 道题,基本属于必刷题,帅地打算把 66 道的题解大致过一遍,大家也可以跟着帅地,每日一道刷起来!每道题会提供简单的思路以及测试通过的代码。

问题描述

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

[

[1,2,8,9], 
[2,4,9,12], 
[4,7,10,13], 
[6,8,11,15]

]

给定 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 端打开。


浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报