有序矩阵查询某值是否在阵中（搜索）

最新推荐文章于 2025-04-11 21:53:26 发布

小胡同的诗

最新推荐文章于 2025-04-11 21:53:26 发布

阅读量432

点赞数

分类专栏： DFS 思维剑指Offer NowCoder

本文链接：https://blog.csdn.net/calculate23/article/details/96305172

版权

思维同时被 3 个专栏收录

59 篇文章

订阅专栏

DFS

57 篇文章

订阅专栏

NowCoder

24 篇文章

订阅专栏

本文介绍了一种在二维有序数组中查找特定整数的方法。利用数组的排序特性，通过深度优先搜索策略实现高效查找，时间复杂度为O(max(row,col))。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

思路：由于是有序的，我们找个起点开始搜索，注意这个起点一定要能确定一个方向是递减一个是递增的，不然两个决策一样地话就不能搜索了，于是找了右上角作为起点dfs,复杂度 $O (m a x (r o w, c o l))$

Code:

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        return dfs(target, array, 0, array[0].size()-1); //O(n)
    }
    
    bool dfs(int target, vector<vector<int> > &arr, int x, int y) {
        if (x == arr.size() || y < 0) return false;
        if (arr[x][y] == target) return true;
        if (arr[x][y] > target) return dfs(target, arr, x, y-1);
        return dfs(target, arr, x+1, y);
    }
};