两有序数组，长度分别m,n，求交。

求世界上最快算法。比O(m+n)快的。

• MSRA的面试？ (48) Robin47 2008-10-23 12:06:10
  • 不是， (0) lastview 2008-10-23 15:07:04
    • 这么多大牛都做不出来，难道我被忽悠了？？ (0) lastview 2008-10-23 15:10:00
    • 百度的。。好像只能针对某些情况来优化。。。 (0) sunny_fable 2008-10-23 21:19:55
• 我不认为在不扫全两个数组的情况下可以精确的求交 (48) wywcgs 2008-10-23 17:13:55
  • 或者说两个完全相同的数组，答案的规模本身就是O(n+m)量级的，不可能会比这个还快 (0) wywcgs 2008-10-23 17:16:22
    • Re:弱弱的问下交是什么?排序? (0) MasterLuo 2008-10-23 17:36:28
      • 求两个数组里面共有的数吧 (0) xwbsw 2008-10-23 17:39:12
      • 集合求交…… (0) wywcgs 2008-10-23 18:40:36
      • 小弟,..... (0) caizhicong0503 2008-10-23 18:54:07
  • Re:我不认为在不扫全两个数组的情况下可以精确的求交 (5) testcase 2008-10-24 16:21:21
• 如果真的有比O(m+n)快的那应该是考虑:两"有序"数组,根据有序不知能否进行优化呢。。。还是说有序的本来就是o(n+m).其实我不懂，只是-____-弱弱发下见解 (48) majia5 2008-10-23 17:41:10
• Re:请教高手一个面试题 (249) zyl072 2008-10-23 18:04:05
  • Re:感觉这个在一般情况下复杂度会比O(N+M)更高。 (213) MasterLuo 2008-10-23 18:11:02
    • 其实也不会,加一点特殊判断就行了 (150) zyl072 2008-10-23 18:26:16
  • 非降序也属于有序吧。这样你的A[i]-A[j]=i-j就没有什么意义了，因为可能有重复元素 (209) wywcgs 2008-10-23 18:39:25
    • Re:O(1)时间就可以判断出来是降序还是升序 (0) MasterLuo 2008-10-23 18:42:59
      • 我是说非降序或非升序。也就是重复元素 (0) wywcgs 2008-10-23 18:44:01
      • increasing 和 not decreasing的区别 (0) wywcgs 2008-10-23 18:44:50
• 如果一个数组小，一个数组大，那么可以加个二分查找 (48) sunmoonstar 2008-10-23 18:10:13
  • 您的意思是,假如N=10 ,M=10000,就可以转化成 N*LogM ,就比N+M更小么? 感觉还是只能在某些特定的情况下才会存在更优算法,低于(M+N)的通用算法还是没想出来..感觉不大可能的样子 (100) zyl072 2008-10-23 18:30:26
    • 本来就不可能，答案规模完全可以是O(n+m) (104) wywcgs 2008-10-23 18:41:31
      • Re:本来就不可能，答案规模完全可以是O(n+m) (54) zyl072 2008-10-23 18:52:33
        • Re:本来就不可能，答案规模完全可以是O(n+m) (64) crazyb0y 2008-10-23 18:55:13
        • 既然在讨论一般情况，我想我们所说的O(m+n)应该就是worst case的复杂度 (58) wywcgs 2008-10-23 19:09:05
• Re:咱们不会被忽悠了吧？ 也许这道题就是为了要说明要学会怀疑。 (48) MasterLuo 2008-10-23 18:52:12
  • 我对天发誓，这绝对是我今天去面某搜索引擎的最后一题 (17) lastview 2008-10-23 19:07:25
    • 以前见过这道题，没讨论出什么所以然。您没问他们的答案是什么？ (21) wywcgs 2008-10-23 19:09:38
      • Re:没，当时只问了啥时候会给我拒信。 (0) lastview 2008-10-23 19:14:50
    • Re:我不是说你忽悠我们。我是说题。 (21) MasterLuo 2008-10-23 19:15:40
      • 会不会是二分后优化之类的？ (0) ACM06060 2008-10-23 19:20:58
        • 比如假定N<M时 T(N,M)=logN+2*T(N,M/2), 而T(1,1)=1 时是否可以推出T(N,M)=min(N,M). (0) ACM06060 2008-10-23 19:36:03
          • Re:比如假定N<M时 T(N,M)=logM+2*T(N,M/2), 而T(1,1)=1 时是否可以推出T(N,M)=min(N,M). (38) lastview 2008-10-23 19:40:25
            • 应该是对的吧，每次那大的找中点，往小的里面去二分，这样一定能保证是min(n,m)的。 (0) ACM06060 2008-10-23 19:43:21
• Re:请教高手一个面试题 (30) re_new 2008-10-23 20:52:59
• 我面试过这道题，说说我的解答。 (323) tq 2008-10-24 12:19:09
  • 我郁闷了，估计就是你这样。他当时跟我说是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