> 两有序数组，长度分别m,n，求交。
> 
> 求世界上最快算法。比O(m+n)快的。

是在百度面试时被问到的。不过直接是说，查询两个关键词，每个关键词的索引返回一个有序数组，然后求两个数组的查询结果的交集。数组长度分别为m和n.

解答：
1. 如果m和n规模一样，则可以直接归并，复杂度为O(m+n)
2. 如果m 远大于n,则对于n中的每个元素，在m中用二分查找，复杂度n*log(m)
3. 如果n 远大于m,则对于m中的每个元素，在n中用二分查找，复杂度m*log(n)

2，3两种情况下的处理方法都比O(m+n)快。
另外前提也说了，两数组必须有序。

当时感觉面试官比较满意这个解答，不知道对不对。

• 我郁闷了，估计就是你这样。他当时跟我说是m>n，我就一直没想明白为什么要这条件。 (16) lastview 2008-10-24 13:27:22
  • 他也没给我说远大于，你面试的时候得多问，多把想法提出来。 (18) tq 2008-10-24 15:11:49
• 不错不错! (301) caizhicong0503 2008-10-24 13:32:48