1楼 [报告]

发表于 2006-12-14 10:47 |显示全部楼层

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

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

2楼 [报告]

发表于 2006-12-15 12:13 |显示全部楼层

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

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

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

3楼 [报告]

发表于 2006-12-15 12:18 |显示全部楼层

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

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

恩, heap..看过一次, 现在已经忘记差不多了...名字都记不住了....刚才想了至少半个小时才....太丢人了

一个google intern的面试题 [复制链接]