uva 1608 不无聊的序列

紫书上有这样一道题:

首先,在整个序列中找到只出现一次的元素ai。如果不能找到,那它就是无聊的。不然,就可以退出当前循环,递归判断[1, i-1]和[i+1, n]是不是无聊的序列。

然而怎么找ai很重要。如果从一头开始找,那么最差情况下的时间复杂度就是O(n^2)的。而如果从两头开始找,那么最差情况就变成了ai在中间,时间复杂度是O(nlogn)!这是因为在中间的找起来慢,分起来快,而在两端的找起来快,分起来慢。有些时候用好中途相遇法还是很重要的。

05-21 13:14