一个google intern的面试题

frog_skywalker

正整数集合s={a1,a2...an}
存在ai*aj=ak, i!=j!=k
求最大的ak


想不到什么好的办法，加法还好办点
现在我是排序，从最大的开始找。
要找的数开根号，以此分成高列，低列。从中间开始乘，往两边移动。


感觉应该有o(n)的方法~~~牛人们看看

Edengundam

我比较笨...只找到了o(n^2)的办法...

建立2颗 AVL 树. 一颗是这个整数集合的, 一棵是2个数的乘积. 计算时候遇到ai == 1 || aj == 1 || ai == aj就不存储乘积了.
建立之后, o(1) 时间取得两颗树的最大值进行比较, 相等时候得出要求的 ak....

frog_skywalker

n^2的算法有很多
有没有效率更高点的

frog_skywalker

顶一下

cjaizss

不存在o(n)的算法

softsongs

a1....an, 一共有n个元素，任意两个元素相乘，有n(n-1)/2 个结果，
想要找出最大的ak , 使得ak = ai* aj, 并且， i != j != k; 那么至少我们需要遍历一遍 这n(n-1)/2 个结果，因为每一个结果都有可能是我们要找的ak。
所以复杂度最少为o(n^2).

ArXoR

原帖由 softsongs 于 12/15/06 11:06 发表
a1....an, 一共有n个元素，任意两个元素相乘，有n(n-1)/2 个结果，
想要找出最大的ak , 使得ak = ai* aj, 并且， i != j != k; 那么至少我们需要遍历一遍 这n(n-1)/2 个结果，因为每一个结果都有可能是我们要找的 ...

可能结论是对的，但是论证方法不对。
而且o和O不是一个概念。。。o(f(n))和O(f(n))不一样的

按这个方法我们讨论一下单源最短路问题，不妨限制在完全无向图G，|G|＝n里，给定源点s
G共有n个节点，任意从s出发的简单路有(n-1)!条，共有(n-1)!个结果
想要找到最短的简单路，那么我们至少要遍历一遍这(n-1)!个结果，因为每个结果都有可能是我们要找的。。。
所以完全无向图上单源最短路问题复杂度至少O((n-1)!)?

明显是不对的，如果要证明复杂度下界，一个可能容易一点的间接的方法就是把其他问题复杂度下界已经证明的问题规约到这个上，产生矛盾才行，比如基于比较的排序算法复杂度复杂度下界是O(nlogn).

对于这个问题。。。至少我还没想到怎么证明其下界是O(n^2).

Please correct me if I'm wrong.

ArXoR

原帖由 Edengundam 于 12/14/06 10:47 发表
我比较笨...只找到了o(n^2)的办法...

建立2颗 AVL 树. 一颗是这个整数集合的, 一棵是2个数的乘积. 计算时候遇到ai == 1 || aj == 1 || ai == aj就不存储乘积了.
建立之后, o(1) 时间取得两颗树的最大值进行 ...

基于二叉搜索树的操作复杂度都是O(logn)的，怎么在O(1)内完成？
难道可以O(n)建一棵树，然后O(n)完成最大值的输出？
这样我们就可以找到一个基于比较的排序算法复杂度是O(n)了，这是不可能的，因为其下界已经证明了是O(nlogn)

你的复杂度应该是O(n^2 * logn)

Edengundam

原帖由 ArXoR 于 2006-12-15 11:50 发表


基于二叉搜索树的操作复杂度都是O(logn)的，怎么在O(1)内完成？
难道可以O(n)建一棵树，然后O(n)完成最大值的输出？
这样我们就可以找到一个基于比较的排序算法复杂度是O(n)了，这是不可能的，因为其下界已 ...

确实是我说错了, 我实际是想用 heap (抱歉我记成AVL....了). 这样我能保证取最值是O(1).

ArXoR

原帖由 Edengundam 于 12/15/06 12:13 发表



确实是我说错了, 我实际是想用 heap (抱歉我记成AVL....了). 这样我能保证取最值是O(1).

。。。还是不行，取完最值还得维护堆性质。。。还要O(logn)...^_^