刷题笔记：二维数组中的查找（C++）

62 阅读 0 评论 41 点赞

我是靠谱客的博主开放棉花糖，最近开发中收集的这篇文章主要介绍刷题笔记：二维数组中的查找（C++），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

剑指OFFER刷题笔记

题目描述

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

解题思路

由于每行每列均渐渐增大。将搜索范围设定为一个矩形，将矩形右上角的值与target进行比较。
将矩形右上角的值与target进行比较，若右上角的值大于target，继续缩小列数；
若大于target值，则当前行的每个值均小于target值，则缩小矩形行数。
以此类推直至搜索到target值返回true；
若搜索矩阵消失，则返回false

图解

（图片摘至网络）

若在矩阵中搜索目标值target=7

代码段

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows=array.size();        //目标矩阵的行数
        int cols=array[0].size();     //目标矩阵的列数
        if(!array.empty() && rows>0 && cols>0){    //目标矩阵是否合法
            int row=0;
            int col=cols-1;
            while(row<rows && col>=0){    //搜索矩阵的范围没有合法
                if(array[row][col]==target)        //成功找到目标值
                {
                    return true;    
                }
                else if(array[row][col]>target)
                {
                    col--;
                }
                else
                {
                    ++row;
                }
            }
            
        }
        return false;
    }
};