这是崔斯特的第一百零九篇原创文章
努力、奋斗 (๑• . •๑)
二维数组中的查找
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如下面的二维数组,如果查找7,返回true,查找5,返回false。
1 | 2 | 8 | 9 |
---|---|---|---|
2 | 4 | 9 | 12 |
4 | 7 | 10 | 13 |
6 | 8 | 11 | 15 |
分析
寻找目标数字b,从数组中选一个数字a,如果a=b
,结束查找;如果a>b
,那么接下来查找的范围就是a的左边或上边;如果a<b
,那么接下来搜索范围就是右边或下边。
当我们需要解决一个复杂的问题时,一个很有效的方法就是从一个具体的问题入手。本题可以从查找数字7入手,一步步分析过程。如果我们在二维数组中间随机选一个数字,那么下次搜索范围就是两个区域,而且有重叠。如果从数组的某一个角上开始搜索,就不会遇到这个问题。
比如从数组右上方开始,
- a=9,b=7,
a>b
,接着查找左边和上边,由于没有上边,所以只能查找左边,也就是1、2、8这三列 - a=8,
a>b
,接着查找左边和上边,因为没有上边,只能接着找左边,也就是1,2这两列 - a=2,
a<b
,接着就是右边和下边,右边已经查找过,所以接下来就是一直往下查找,也就是1、2这两列的下方 - a=4,
a<b
,接着查找1、2这两列的下面两行 - a=7,
a=b
,结束查找。
解法
从二维数组的右上方开始查找:
- 若元素值等于
target
,返回true
; - 若元素值大于
target
,砍掉这一列,即--j
; - 若元素值小于
target
,砍掉这一行,即++i
。
也可以从二维数组的左下方开始查找,以下代码使用左下方作为查找的起点。
注意,不能选择左上方或者右下方的数字,因为这样无法缩小查找的范围。
|
|
如果是我自己去写这道题的话,肯定想不出这样的方法,可能就是遍历所有数字,这肯定不是面试官要问的。看了书中介绍的方法,分析过程确实很重要,一步步去寻找规律。我想起了高中数学的
数列
,老师常说“数列就是列数,如果不知道规律,就多写几个例子”。对于现在的这种算法题,一定要多试几个例子,从中找到规律。