剑指offer(C++)-JZ4:二维数组中的查找(算法-搜索算法)

简介: 剑指offer(C++)-JZ4:二维数组中的查找(算法-搜索算法)

题目描述:

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

[


[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]


]


给定 target = 7,返回 true。


给定 target = 3,返回 false。


数据范围:矩阵的长宽满足0≤n,m≤500 , 矩阵中的值满足0≤val≤109

进阶:空间复杂度O(1) ,时间复杂度O(n+m)

示例:

输入:

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


返回值:

true


说明:

存在7,返回true

解题思路:

本题考察算法-搜索算法的使用。考虑到复杂度的要求,最多走一行一列的时间,结合二维升序数组的特性,是可行的,具体思路如下:


  1. 判断行列数是否正常。
  2. 以左下角为起点开始找。
  3. 若是目标值小于当前值,往上跑,因为右边的值更大;若是目标值大于当前值,往右跑,因为下面的值更小。(其实和二分思想类似,一步步压缩可选的范围)
  4. 从左下跑到右上,如果没找到目标值,那就是没有了。

测试代码:

class Solution {
public:
    // 寻找目标值
    bool Find(int target, vector<vector<int> > array) {
        // 判断行列数是否大于0
        if(array.size() == 0)  
            return false;
        if(array[0].size() == 0)  
            return false;
        // 记录行列数
        int row = array.size();
        int col = array[0].size();
        // 从最左下角的元素开始往左或往上
        for(int i = row - 1, j = 0; i >= 0 && j < col; )
        { 
            // 目标值小于当前值,那就往上走,因为右边全是比目标值大的数值
            if(array[i][j] > target)   
                i--;
            // 目标值大于当前值,那就往右走,因为上边全是比目标值小的数值
            else if(array[i][j] < target) 
                j++;
            // 锁定目标值,返回true
            else
                return true;
        }
        // 遍历完没找到目标,返回false
        return false;
    }
};


相关文章
|
17天前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
|
9天前
|
机器学习/深度学习 人工智能 分布式计算
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
机器学习中的超参数调优是提升模型性能的关键步骤,包括网格搜索、随机搜索、贝叶斯优化和遗传算法等方法。网格搜索通过穷举所有可能的超参数组合找到最优,但计算成本高;随机搜索则在预设范围内随机采样,降低计算成本;贝叶斯优化使用代理模型智能选择超参数,效率高且适应性强;遗传算法模拟生物进化,全局搜索能力强。此外,还有多目标优化、异步并行优化等高级技术,以及Hyperopt、Optuna等优化库来提升调优效率。实践中,应结合模型类型、数据规模和计算资源选择合适的调优策略。
14 0
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
|
14天前
|
算法 C++
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
22 2
|
14天前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点,算法规划路径并显示长度。测试显示,尽管在某些复杂情况下计算路径可能与实际有偏差,但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论,不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好,但在交通拥堵等特殊情况下需结合其他数据提升准确性。
|
16天前
|
搜索推荐 算法 C++
|
16天前
|
存储 算法 Serverless
|
16天前
|
存储 算法 搜索推荐