我觉得只能进行一点优化而已吧?

比如说,A B两个有序的数组,假如存在 (i>j)  A[i]-A[j]=i-j  则说明 A[i]->A[j] 一定是连续的数字段,这个时候一定包含了从A[i]到A[j] 的每一个元素,B数列也是一样.具体用法,目前也只想到用二分的方式来选取以A[i]为起始位置的连续的数字段. 当然这只能是针对一些连续的数字段的优化.在最坏的情况下,效率依然不怎么样~

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

• 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