本文共 998 字，大约阅读时间需要 3 分钟。

二维数组中的查找的两种解法及C++实现

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组，判断数组中是否含有该整数。

例如下面二维数组每行递增、每列都递增。如果从这个数组中查找数字7，则返回true；如果查找数字5，则返回false

1 2 8  92 4 9  124 7 10 136 8 11 15

解法1：暴力法

从数组中挨个扫描，如果找到返回true，否则返回false（只是为了对比，不建议）

class Solution {
   public:    bool Find(int target, vector
   
    
      > array) {
           int i,j;        for(i=0;i
    
   

代码运行结果：

解法2：排除法

对于这样的一个数组，我们可以拿右上方向对角线上的元素考虑：

• 如果该数字等于要查找的数字，则查找完成
• 如果该数字大于要查找的数字，则去掉这一列（因为这一列的数据依次递增），缩小查找范围
• 如果该数字小于要查找的数字，则去掉这一行（因为这一行的数据从右到左依次递减）

即每次要查找的数字不在右上角，则都可以去掉一行或者一列，从而缩小查找范围

牛客网提交代码如下：

class Solution {
   public:    bool Find(int target,vector
   
    
      > array){
           int r=0,c=array[0].size()-1;        while(r
     
      =0){
               if(array[r][c]==target){
                   return true;            }else if(array[r][c]>target){
                   c--;            }else{
                   r++;            }        }        return false;    }};
     
    
   

代码运行结果：

《剑指Offer》面试题4

转载地址：https://blog.csdn.net/Jeaten/article/details/107891633 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！