今日面试题:七夕鹊桥

有n对喜鹊。每一对可以表示为(x,y),x、y是喜鹊的编号,并且任意一对,x总是小于y。(c,d)可以连接在(a,b)之后,当且仅当b

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

数字游戏分析

原题

盒子中有n张卡片,上面的数字分别为k1,k2,...,kn。你有4次机会,每抽一次,记录下卡片上的数字,再将卡片放回盒子中。如果4个数字的和等于m。则你就赢得游戏,否则就是输。直觉上,赢的可能性太低了。请你给出程序,判断是否有赢的可能性。尽量提高方法的效率。

分析

这个题目,和之前Google的一个概率的题目是类似的,当然解决的方法也是类似的,思路大家可以找找前面的题目,不再赘述。

这个题目其实想和大家讲一下思考问题、改进解法的思路。

这个题目最直接的方法就是四重循环遍历,n^4的时间复杂度,比较恐怖,但确实一个很好的起点。不用觉得很丢人,只要我们持续改进即可。

假设a,b,c是k1到kn中的三个数字,是否存在d使得,a+b+c+d=m?d在k1到kn中。和题目中的意思是一样的,变换等式如下:

d = m - a - b - c

如果满足上式,就是说,要在k1到k2中查找d,即:查找m - a - b - c,找到就存在;找不到,就是不存在。查找有线性查找,二分查找等。四重循环最内一层循环,可以认为是线性的查找,如果想更快一些,可以应用二分查找,而二分查找需要k1到kn是排序的,则先对n个数字进行排序,时间复杂度O(nlogn)。然后最内一层循环,改为二分查找,时间复杂度为O(n^3logn)。所以总的时间复杂度为O(n^3logn)。

经过上面的分析,我们可以得到启发,既然可以提出一个d,那么就可以再提出一个c。将a+b+c+d=m转换为c+d=m-a-b。这样,我们可以枚举k1到kn的两个数的和,然后对n2个和,进行排序,时间复杂度为o(n^2logn)。然后遍历n^2个和,设每一个和为pair,查找是否存在m-pair,同样二分查找,时间复杂度为O(n^2logn)。总的时间复杂度为O(n^2logn)。

经过上面的层层分析,大家能否发现,对于算法的持续改进,还是有一些窍门的,大家细心领悟。领悟得多了,必会有更大的进步。

这个题目其实解法比较多,出了上面介绍的,还有别的方法,比如应用一些数据结构。大家可以开动自己的脑筋,不断的发散。不要为了完成一个题目而去思考。应该尝试不同的思路,即使思路的时间、空间的复杂度并不好,但是只要能够分析清楚。这就是很大的进步。这些也是我们给大家介绍面试题的一个初衷。我们尽可能的将问题分析透彻,希望能够给大家以启迪。

【分析完毕】

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