GNote.Net | 记笔记

昨天同学去google笔试，我好奇的问了问笔试题目。
有一道题是这样的：
两个相同长度的整型数组A、B，长度为n。现从两个数组中，各抽出S个数，形成两个新的数组C、D。
实现一个算法，保证数组CD的内积最大，并分析时间和空间复杂度。

我说了一个解法，被同学指出复杂度高，于是又验证了同学的解法，确实更快。
我的解法如下：
先考虑一下，当CD两个数组确定后，如何排列里面的元素可以使内积最大。
假设数组中只有两个元素C1C2和D1D2，并且C1 > C2 && D1 > D2，则可以证明 C1*D1 > C2*D2
如此推广开，就是大的乘大的，小的乘小的，可以保证内积最大。

第二步，如何从两个数组中取出S个数。
考虑到整数的正负符号问题，负负得正，所以我先用绝对值从大到小排序，得到两个数组A’和B’（这个复杂度是nlgn）
然后从大到小遍历A’，每访问到一个数a，就从B’中找一个数可以和a相乘得到最大值。
如此继续2*S次，然后从结果中选出值最大的S对就是答案了（这一步的复杂度为n^2）。

同学的想法是：
直接将两个数组按大小排序，然后从数组两头向中间各取S个数，相同下标的相乘，从结果中选出值最大的S对就是答案。整个过程的复杂度都在nlgn这个量级上。

Trackback URI | Comments RSS