[面试题] 求数组两两之差绝对值最小的值(Update Version) - HappyAngel - 博客园
由于准备找工，最近也用零星的时间做了一些面试题，这道题属于偏难的那种了，之所以说它偏难，主要是因为按常规思维不容易得到最优解，更重要的是，此题的转化不容易想到。做过编程之美的同学都能了解到，很多题目都需要一种"转化"的思想，把问题转化为另一种已知的熟悉的问题去求解，这种思路在《如何解题》也是被提到了很多次，不过实施起来真的不容易。
一 题目描述：
有一个整数数组，请求出两两之差绝对值最小的值，只要求出最小值即可，不要求求出是哪两个数。
二 常规思路：
求解此题的寻常思路是什么？观察题目我注意到后面强调不要求求出两个数，那么最最简单的O(n^2)的算法显然做了很多无用功。嗯，好，既然这个办法不行想想其他的。对于数组也就是序列之类的题，有一种很常用的思路那就是预处理。这道题目貌似是可以的。
首先，对数组进行排序，这个可以在O(n*logn)时间之类解决，然后，有了这个预处理，就会想到，绝对值之差最小值肯定只能发生在预处理的数组之后的相邻的元素上，这个是很显然的事实。那么我们便可以循环一遍数组，记下两两之间绝对值的最小值，那么所求得到值便是解答，总的时间复杂度是O(n*logn)。仔细想想这种方法，很明显，排序减小了我们所需要搜寻的解空间，从而达到了减小时间复杂度的目的。不过这个解法仍然不能让人满意，因为我们还是浪费时间求出了最终的两个元素，而题目不要求，所以，这肯定不是最优解。
三 转化的思想
再仔细观察题目，我们可以猜到，最优解应该是只求出最小值而不求出具体的元素的，那么该怎么做呢？我们可能能想到用辅助数组，但是却很难想到怎么做这个辅助。其实这道题我一直在思考如何通过常规的思维去想到这个最优解，不过我当时没有想出来，而这才是我写这篇博客的原因，即促使我了解并对这种思路印象深刻，不过这可能只适用于解这题或者类似能让我联想到这种方法的题，这背后更一般的思维（可以叫做转化，但是还可以更具体些）我还没有想到，希望想到的同学联系我！。
好了，本题要做的辅助数组是这样一个数组，设它为Bn.原来题目中给定的数组是An,则Bn等于：
B1 = A1 - A2;
B2 = A2 - A3;
B3 = A3 - A4;
......
Bn-1 = An-1 - An.
注意，Bn的长度是n-1，正好比An要小一个。聪明的同学看到这个辅助数组，立马就能猜到原因了，因为这样做的话，我们能够把这道看似无从下手求出最优解的问题转化为求Bn的绝对值最小的最长连续子序列和，因为Bn的连续子序列和便是An任意两数之差（注意，由于题目要求的是绝对值最小，所以求出A1-A2等效于得出A2-A1），例如：
A2 - A5 = B2 + B3 + B4 = A2 - A3 + A3 - A4 + A4 - A5 = A2 - A5
实际上，任何Ai - Aj（i<j） = sigma(k=i -> k=j-1)(k)
这样的话，我们就成功把问题转化为了连续子序列问题，不过和我们以前做的最大或最小连续子序列还不完全相同，此处是绝对值最小。那么怎么样的值可能是绝对值最小呢？正数最小或者负数最大，也就是说在数轴上离0更近的数其绝对值更小，基于此我们可以得到如下的方法。
和原来求最大连续子序列和一样，要用数学归纳法思考，我们直接看归纳基础，
归纳基础： 假设已知B1..Bk的绝对值最小连续的连续子序列和是Min(Bk)
我们利用这个求解B(k+1)，加入B(k+1)后有可能比Min(Bk)小的只可能是以B(k+1)结尾的绝对值最小的连续子序列和，如果把这个和Min(Bk)比较就可以知道是否需要更新Min(Bk)。所以，我们加强这个归纳基础。
更强的归纳基础： 假设已知B1..Bk的绝对值最小连续的连续子序列和Min(Bk)，以及以Bk结尾的绝对值最小连续子序列和Suffix(Bk)
有了这个归纳，我们可以去想如何维护这个Suffix(Bk),目标是使的Suffix(B(k+1))仍然是以B(k+1)结尾的最小连续子序列和。如果按照求最小和的思路，那便是只要Suffix(Bk)是正数便置它为0，因为如果它是正数，那么在后续求Suffix(B(k+1))时就肯定比用0要更大，因为正数会使得整个值变大，而0不会。同样的道理，我们只要使得求Suffix的时候比直接置0更小即可，否则我们可以直接把Suffix(B(k+1))置0以获得更小值。由于我们求的是绝对值最小，直接按最小值的思路是不行的，因为可能某个Suffix是暂时求得一个很小的负数，下次加上某个正数会使得它成为很小的正数，所以不能以正数负数作定论而要以与0的距离。所以我们应该采取比较符号的方法，如果当前suffix和下一个数的符号相反，那么可以继续相加以求得下一个suffix，因为我们可以获得绝对值更小的suffix；如果是同号，无论正负一定会比把当前suffix置0更糟糕，因为这将使得下次的suffix在数轴上离0更远。所以我们维护Suffix的公式如下：
Suffix(B(k+1)) = Suffix(B(k)) + B(k+1）， if (Suffix(B(k))*B(k+1)) < 0
Suffix(B(k+1)) = 0, if (Suffix(B(k))*B(k+1)) ) > 0
这样我们一直归纳下去，便可以求得最终的Min(Bn)，即可求得解。整个的时间复杂度是O(n),空间复杂度是O(n)。
(Update)经过昨晚的思考以及和网友fuwutu童鞋的讨论，我此处归纳的过程是有问题的，同时对O(n)算法的存在性也产生了怀疑。问题的关键在于，Suffix(k)不仅仅受Suffix(k-1)影响，还受前面的Suffix影响，例如{-1,-1,2}，明显的这个例子的答案是0，单纯看第二个-1，它的最小的绝对值是选择自己即-1，然而后续2需要-1选择和前面的和累加得到-2从而得到最终的答案0，换句话说，从DP的角度讲，这道题不满足无后效性，其某一状态并不仅仅受前一状态的影响，即便给你绝对值最小的Suffix(k)也无法推出Suffix(k+1)。所以，直接归纳是不可行的。那么能不能对绝对值最小值这个问题进行转换呢？我想到的是按情况分，例如如果数组全是正数或者负数，可以直接以最小值或最大值的子序列和算法求，如果既有正数又有负数，就要用其他方法处理。此处更新在于说明我归纳的错误同时不让更多的同学产生错误的想法（对于没有仔细思考问题的同学 :) ），也非常感谢大家的指正，让我能够更加仔细的反思自己的思考过程，从而提高自己，谢谢大家啦 :)。
五 总结
Read full article from [面试题] 求数组两两之差绝对值最小的值(Update Version) - HappyAngel - 博客园
No comments:
Post a Comment