二维数组中的查找

题目描述

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

问题分析

如以下表格,我们把它当成一个为维数组。它的特征是从左到右递增,从上到下递增。

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

首先我们需要寻找一个切入点来遍历二维数组,那么我们会考虑选择四个角1,9,6,15的位置。1是二维数组中最小的,15是二维数组中最大的,可能很多人会首先选择这两个的一个来作为遍历的起点。

假如我们现在选择1来作为起点,若目标整数比1小或等于1,那我们可以直接得出结论。若目标整数比1大,那么我们既可以向右遍历,也可以向下遍历,这样就很麻烦了。选择15作为起点同理。

如果我们选择9或者6呢?如果选择6作为起点,若目标整数等于6则可得出结论,若目标整数比6小,那么6的这一行数都是比6大的,可以直接抛弃。若目标整数大于6,6的这一列都是小于目标整数的,则可以直接抛弃。

很明显,选择1或者15作为起点是十分尴尬的。接下来我们来分析一下,目标整数是5的情况。

6>5,抛弃6的这一行,向上遍历;

4<5,抛弃4的这一列,向右遍历;

7>5,抛弃7的这一行,向上遍历;

4<5,抛弃4的这一列,向右遍历;

9>5,抛弃9的这一行,向上遍历;

8>5,抛弃8的这一行,数组已遍历完,不存在5。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean find(int target, int[][] array) {
int j = array.length - 1;
int i = 0;
while(j >= 0 && i < array[j].length) {
if (target < array[j][i]) {
j--;
} else if (target > array[j][i]) {
i++;
} else {
return true;
}
}
return false;
}
-------------本文结束感谢您的阅读-------------

本文标题:二维数组中的查找

文章作者:huihui

发布时间:2018年10月18日 - 15:10

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2018/10/18/二维数组中的查找/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。