题解:当然可以O(nk)的效率,但是这样很low,我们可以用O(nlog(k))的效率去解决。
首先按照暴力的思想,从一个元素x开始,遍历它后面的k-1位元素,判断是否有符合的条件。如果将这个k个数排序的话,就不用遍历啦,只要找到x的位置,然后判断x的前后是否满足条件皆可以了。
但是如果对于每一个x都要排序k个元素,那么效率就是O(nklog(k)) 还不如暴力。所以我们不能这样每次都排序,因为从左往右,当x+1之后,需要排序的k个数只是增加了一个数,减去一个x而已,所以在原先k个有序元素的基础上,加上一个数,删除去一个数的效率是可以O(logk)实现的,比如平衡二叉搜索树AVL,我们可以用multiset,内部实现是红黑树。
typedef long long int _int;
class Solution {
public:
multiset<_int> m;
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int i;
for(i=0;i<nums.size()&&i<k+1;i++)
{
m.insert((_int)nums[i]);
}
for(int i=0;i<nums.size();i++)
{
if(m.size()<=1)
break;
multiset<_int>::iterator it = m.find((_int)nums[i]);
if(it!=m.begin() && abs((*prev(it))-(*it)) <= (_int)t)
return true;
if(next(it)!=m.end() && abs((*next(it))-(*it)) <= (_int)t)
return true;
m.erase(it);
if(i+k+1< nums.size())
m.insert((_int)nums[i+k+1]);
}
return false;
}
};