数组中重复的数字
解题思路
数组类题目解题往往是存在直观解法的,因为不管是一维数组还是二维数组,都可以直接通过双重for
循环之类方法进行直接求解,但是这种解法的时间复杂度都是很高的,为此,在算法类题目中涉及到数组,往往不会使用多重循环求解。
代码实现
但是在一步步求解过程中,还是需要思路循序渐进,因此还是从最直观的解法入手一步步进行优化。
上述题目最直观的解法如下:
1 | public static boolean duplicate(int[] numbers, int length, int[] duplication) { |
一个双重for
循环可以直接搞定,但是问题来了,上面解法时间复杂度显然为O(n^2)
,这种复杂度对于海量数据求解来说,是很不可取的。
那么我们可以再次进行优化一下,我们可以对数组进行排序,这样算法复杂度会降低,于是可以以下面代码实现:
1 | public static boolean duplicate(int[] numbers, int length, int[] duplication) { |
但是上述还不是最优解,假如我们要求时间复杂度为O(n),空间复杂度为O(1)
,在这个前提下,我们需要再寻求一种最优解。
那么我们需要注意到题目中有一个条件是长度为n的数组里面所有数字都在0~n-1范围内,这个条件肯定不是白给的,上面两种解题思路都没有用到这个条件,那么这个条件肯定就是解题的关键。
根据上面思路,如果这个数组中没有重复的数字,那么当数组排序后,数字i
将出现在下标为i
的位置,但是由于数组中一定有重复的数字,那么有些位置可能存在多个数字,同时有些位置可能没有数字。
比如对于数组[2,3,1,0,2,5,3]
- 首先从头到尾扫描这个数组,当扫描到下标为
i
的数字时,比较这个数字(比如为m
)是不是等于i
。 - 如果是,那么接着扫描下一个数字
- 如果不是,那么拿这个数字跟第
m
个数字进行比较。 - 如果这个数字跟第
m
个数字相等,那么这个数字就是其中一个重复数字,结束寻找 - 如果不等,将把第
i
个数字和第m
个数字交换,即把m
放到属于它的位置 - 重复上述过程,直到发现一个重复的数字。
根据上述思路,我们可以写出最终优化的代码如下:
1 | public static boolean duplicate(int[] numbers,int length,int[] duplication) { |
二维数组的查找
解题思路
那么显然同上一题,这个题还是可以通过双重for
循环直接解决,并且代码十分简洁。但是还是那个问题,最直观的解法往往不是最优解,题目给了那么多条件,仅仅通过一个双重for
循环完成,时间复杂度是非常高的。
代码实现
根据题目条件,实际上不难想出另外一种解法:
比如对于如下二维数组,我们要查找数字7
:
1 | 1 2 8 9 |
由于数组从左到右递增,从上到下递增,我们可以试图先选一个边角的值,比如右上角的9
,这个值比它左边的值都要大,比它下面的值都要小。
那么这个值比要找的7
要大,说明7
不可能在9
这一列了,于是我们把这一列去掉。
1 | 1 2 8 |
继续选取右上角的值,我们发现8
还是比7
要大,于是8
这一列的值也可以删掉了。
1 | 1 2 |
然后选取右上角的值2
,由于2
比7
小,那么说明2
所在的一行不可能包括7
,那么把这一行删掉。
1 | 2 4 |
由于右上角的4
比7
要小,那么同样可以删掉这一行。
1 | 4 7 |
最终右上角的值就是我们要找的值,那么这种办法实际上避免了双重循环的冗余度,可以很快的找到是否包括需要查找的值。并且在数据量越大的时候,越能体会到这种算法的时间优越性。这就是算法的实用性所在。
基于上述思路,代码实现可以如下:
1 | public boolean Find(int target, int [][] array) { |
构建乘积数组
解题思路
如果没有不能使用除法的限制,那么这个题目可以直接使用公式解出来,即将(A[0]*A[1]*...*A[n-1])/A[i]
即可得到结果。
既然不能用除法,那么只能寻找其他思路。
- 直接按题目要求连乘,显然时间复杂度为O(n^2)
- 有吗?
当然有,我们基于题目算法可以构建矩阵如下:
其中B[i]的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得,上三角,从下向上也是连乘。
因此我们的思路就很清晰了,先算下三角中的连乘,即我们先算出B[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。
代码实现
基于上述思路,代码实现如下:
1 | public class Solution { |