# 题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
# 问题分析
如以下表格,我们把它当成一个为维数组。它的特征是从左到右递增,从上到下递增。
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。
# 代码实现
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; | |
} |