【一刷《剑指Offer》】面试题 3:二维数组中的查找

简介: 【一刷《剑指Offer》】面试题 3:二维数组中的查找

力扣对应题目链接:240. 搜索二维矩阵 II - 力扣(LeetCode)  

牛客对应题目链接:二维数组中的查找__牛客网 (nowcoder.com)

核心考点:数组相关,特性观察,时间复杂度把握。


一、《剑指Offer》对应内容


二、分析题目

  1. 正常查找的过程本质就是排除的过程,谁排除的效率更高,谁对应查找的效率也就更高。
  2. 如果双循环查找,本质是一次排除一个,效率过低。但采取从右上角 / 左下角进行比较,这样就可以一次排除一行或一列。
  3. 注意临界条件。

三、代码(C++)

1、从右上角开始排查

//从右上角开始排查
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i=0, j=matrix[0].size()-1;
        while(i<matrix.size() && j>=0)
        {
            if(matrix[i][j]>target)
                j--;
            else if(matrix[i][j]<target)
                i++;
            else return true;
        }
        return false;
    }
};

注意:本题因为所提供数据范围为:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300

所以,排除了空数组的情况,否则还需要在开头进行特判。

例如,下面这道题目:LCR 121. 寻找目标值 - 二维数组 - 力扣(LeetCode)

//从右上角开始排查
class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        if(plants.size()==0 || plants[0].size()==0) return false;
        int i=0, j=plants[0].size()-1;
        while(i<plants.size() && j>=0)
        {
            if(plants[i][j]>target)
                j--;
            else if(plants[i][j]<target)
                i++;
            else return true;
        }
        return false;
    }
};

注意:如果采用第二种方法:“从左下角开始排查”,则不需要进行特判,因为如果数组为空,第二种方法并不会进入到循环当中。

//从左下角开始排查
class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        int i=plants.size()-1, j=0;
        while(i>=0 && j<plants[0].size())
        {
            if(plants[i][j]>target)
                i--;
            else if(plants[i][j]<target)
                j++;
            else return true;
        }
        return false;
    }
};

2、从左下角开始排查

//从左下角开始排查
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i=matrix.size()-1, j=0;
        while(i>=0 && j<matrix[0].size())
        {
            if(matrix[i][j]>target)
                i--;
            else if(matrix[i][j]<target)
                j++;
            else return true;
        }
        return false;
    }
};


相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面