今日面试题

求正数数组内和为指定数字的合并总数

例如:[5, 5, 10, 2, 3] 合并值为 15

合并总数为4,分别为:(5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3)

=============================================

相差最大分析

原题

给定无序数组A,在线性时间内找到i和j,j>i,并且保证A[j]-A[i]是最大的。

分析

这个题目是比较简单的。很直接的,对于每一个A[j],如果知道前面的元素中最小的元素min,则此时相差最大为A[j]-min。则,假设有一个数组M,M[j]表示[0,j-1]中最小的元素。这个遍历一边A,就可以完成构造M。再遍历一边数组,就可以找到相差最大的。我们举个例子看看M,以及是否有改进的空间。

假设A={1,2,5,3,4}。通过一次遍历,得到M如下:

1 1 1 1 1

这是一个极端的例子,但确实给了我们一个改进的方向,就是并不需要一个数组保存最小值,而只需要一个变量即可。

上面的例子不明显,假定A={2,5,1,3,4},过程如下:

j A[j] 最小值m A[j]-m
0 2 2 0
1 5 2 3
2 1 1 0
3 3 1 2
4 4 1 3

最终得到相差最大为3.这个例子,可以找到两个i,j。

上面的过程是一个不断改进的一个过程。如果在面试的过程中,能够很好的完成,即使在面试官的指导之下,也是没有问题的。

这个题目,如果有的同学给出数组C,C[j]表示[0,j]中的最小值;数组B表示[j+1, n-1]中的最大值;这两个数组遍历两次可以得到,然后,再遍历一次A,对于每一个i,B[i]-C[i]中最大的,就是最终的值。这个思路也是ok的,只不过比我们开始提到的,更加一些,可以通过观察C,B的变化,找到规律,进行化简。

【分析完毕】

本文来自微信:待字闺中,2013-08-07发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。