首页 > 编程语言 > 详细

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

时间:2020-05-09 22:32:35      阅读:68      评论:0      收藏:0      [点我收藏+]

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

分析:从题干中的标红字体之后,很容易会想到使用二分查找来解决这个问题,所以就变得简单起来

解题思路

  使用for循环依次遍历每一行数组,在每一行中使用二分查找来查看是否存在于这一行。

  但这显然不是最好的解决方案:

  1. 当查找的元素并不存在于二维数组的时候,例如:要查找的是-1,但数组里面都是整数,我们还要全部遍历一遍,这样做了很多不必要的工作。
  2. 如果要查找的实在最后一行,这样我们前面也是做了很多无用功,小的数量不伤大雅,但是如果有1000行呢,就严重的影响了效率。

这里我使用的并不是优化的版本,欢迎各位提出宝贵意见,有关这个题目的。

 1  bool Find(int target, vector<vector<int> > array) {
 2     for (int i = 0; i < array.size(); i++)
 3     {
 4         int left = 0;
 5         int right = array[0].size() - 1;
 6         while (left <= right)
 7         {
 8             int mid = (left + right) / 2;
 9             if (array[i].at(mid) > target)
10             {
11                 right = mid - 1;
12             }
13             else if (array[i].at(mid) < target)
14             {
15                 left = mid + 1;
16             }
17             else
18                 return true;
19         }
20     }
21         return false;
22     }

 

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

原文:https://www.cnblogs.com/jianmoxiansheng-Guo/p/12860253.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!