首页 > 编程语言 > 详细

15. 二维数组中的查找

时间:2020-09-14 14:02:51      阅读:81      评论:0      收藏:0      [点我收藏+]

 

题目描述

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

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

样例

输入数组:

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

如果输入查找数值为7,则返回true,

如果输入查找数值为5,则返回false。

思路

  由题目的描述可知,输入的是一个杨式矩阵(行列都是递增的矩阵),要查找某个数,那么就从对角线上的两个数(右上角或左下角)开始,因为右上角的数是该行最大该列最小的数,而左下角的数是该行最小该列最大的数,以右上角的数为例,若要查找的数小于这个数,那么就往左移动一格继续查找,若大于这个数,那么就往下移动一格继续查找,这样就能在最短时间内判断出矩阵中是否含有我们要查找的数.

  需要注意的是,输入的二维数组可能为空,如下图,所以需要对此先行判断,加上第5行代码即可.

 技术分享图片

 1 class Solution {
 2 public:
 3     bool searchArray(vector<vector<int>> array, int target) {
 4         int n=array.size();
 5         if(!n) return false;//若二维数组为空
 6         int m=array[0].size();
 7         int i=0, j=m-1;
 8         while(1) {
 9             if(i<0 || i>=n || j<0 || j>=m) break;
10             if(array[i][j]==target) return true;
11             if(array[i][j]<target) i++;
12             else if(array[i][j]>target) j--;
13         }
14         return false;
15     }
16 };

15. 二维数组中的查找

原文:https://www.cnblogs.com/wwqzbl/p/13666147.html

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