uva 1608 不无聊的序列
紫书上有这样一道题：
首先，在整个序列中找到只出现一次的元素ai。如果不能找到，那它就是无聊的。不然，就可以退出当前循环，递归判断[1, i-1]和[i+1, n]是不是无聊的序列。
然而怎么找ai很重要。如果从一头开始找，那么最差情况下的时间复杂度就是O(n^2)的。而如果从两头开始找，那么最差情况就变成了ai在中间，时间复杂度是O(nlogn)！这是因为在中间的找起来慢，分起来快，而在两端的找起来快，分起来慢。有些时候用好中途相遇法还是很重要的。
紫书上有这样一道题：
首先，在整个序列中找到只出现一次的元素ai。如果不能找到，那它就是无聊的。不然，就可以退出当前循环，递归判断[1, i-1]和[i+1, n]是不是无聊的序列。
然而怎么找ai很重要。如果从一头开始找，那么最差情况下的时间复杂度就是O(n^2)的。而如果从两头开始找，那么最差情况就变成了ai在中间，时间复杂度是O(nlogn)！这是因为在中间的找起来慢，分起来快，而在两端的找起来快，分起来慢。有些时候用好中途相遇法还是很重要的。