前言
对于剑指offer题解这个系列,我的写作思路是,对于看过文章的读者,能够做到:
- 迅速了解该题常见解答思路(奇技淫巧不包括在内,节省大家时间,实在有研究需求的人可以查阅其它资料)
- 思路尽量贴近原书(例如书中提到的面试官经常会要求不改变原数组,或者有空间限制等,尽量体现在代码中,保证读者可以不漏掉书中细节)
- 尽量精简话语,避免冗长解释
- 给出代码可运行,注释齐全,关注细节问题
- 代码能够通过牛客网在线编程《剑指offer》测试
题目介绍
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解题思路
方法一
首先能够想到的肯定是一行一行或者一列一列遍历,判断数组中是否含有该整数。该方法显然是最笨拙的二维数组遍历,面试官也不会满意,时间复杂度是O(n^2)
代码
Python
class Solution: def Find(self, target, array): for i in range(len(array)): for j in range(len(array[0])): if array[i][j]==target: return True return False 复制代码
方法二
我们思考下,既然大的数字都在靠右边/下边,能否能利用行列的数据变化规律来优化下解法,如果寻找的目标数大于现在的数字,那么目标数字是在当前位置的右边或下边,如果所寻找的目标数小于现在的数字,那么目标数字在当前位置的左边或上边。举个例子,如下图数组所示:
1 2 3 4 2 3 8 9 3 4 9 10 4 5 10 11 复制代码
我们的位置是1,要找8,8大于1,那么在1的右边和下边区域进行下一步的搜索。
如果我们先搜索他的右边,
2 3 4 3 8 9 4 9 10 5 10 11 复制代码
又搜索了他们的下边,
2 3 8 9 3 4 9 10 4 5 10 11 复制代码
这时候我们发现
3 8 9 4 9 10 5 10 11 复制代码
这个区域搜索了两次,我们是从数组的第一个数[0][0]取的,遇到了重复搜索区域的问题。有没有方法去除重复的搜索区域呢,我们发现,当从右上角取第一个数的时候,可以去除重复的搜索区域,还是以这个数组为例,取4,搜索8,发现8比4大,那么8不可能出现在4这一行,只需要从下边搜索即可。如果寻找3,3比4小,4那一列后续的数都大于4,只需要从左边搜索即可。
1 2 3 4 2 3 8 9 3 4 9 10 4 5 10 11 复制代码
我们还可以发现左下角的点也可以去除重复搜索区域,总结起来的话,有点像变量控制法的感觉,将一个变量控制住,根据另外一个变量的规律,得出结论。
这样我们将时间复杂度降为了O(n)
代码
Java
public class Solution { public boolean Find(int target, int [][] array) { int rows = array.length; int cols = array[0].length; int i = rows-1, j = 0; while(i >= 0 && j < cols){ if(target < array[i][j]) i--; else if(target > array[i][j]) j++; else return true; } return false; } } 复制代码
Python
class Solution: def Find(self, target, array): if array == ([] or [[]]): return False row = len(array) col = len(array[0]) i=0 j=col-1 while 0<=i<row and 0<=j<col: if target>array[i][j]: i=i+1 elif target<array[i][j]: j=j-1 else: return True return False 复制代码
总结
题目简单,小伙伴们需要理解的是算法题应该注重的是效率优化,暴力穷举能够解决问题,但说服不了面试官。