Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

其实也不会,加一点特殊判断就行了

Posted by zyl072 at 2008-10-23 18:26:16 and last updated at 2008-10-23 18:27:45
In Reply To:Re:感觉这个在一般情况下复杂度会比O(N+M)更高。 Posted by:MasterLuo at 2008-10-23 18:11:02

对于 A[i] ,假如a[i+1]>a[i]+1 则不用进行这个方法了~~~
否则再进行二分查找来找到结尾元素~~~

对于某些数据这样的算法可能比 (N+M) 更慢,但是对于连续的数字比较多情况下,优势就出来了.
因为他把这个数组划分成了一个段一段的,然后一段一段的处理,处理的次数就会少了

Followed by:

Post your reply here: