C++ n*log(k) solution, explained in the comments


  • 2
    J

    Explained in comments.

    class Solution {
    public:
    	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
    		int size = nums.size();
    		if (k >= size)
    			k = size - 1;
    		if (k <= 0)
    			return false;
    		***// a slide window containing k + 1 item***
    		multiset<long long> window;
    
    		// initilize window and check first window k * log(k)
    		for (int i = 0; i <= k; i++)
    		{
    			window.insert(nums[i]);
    		}
    		auto pre = window.begin();
    		auto cur = ++window.begin();
    		while (cur != window.end())
    		{
    			if (*cur - *pre <= t)
    				return true;
    			pre = cur;
    			++cur;
    		}
    
    		***// slide the window one by one. The window is guaranteed that ele is at least t far away from its neighbors***
    		for (int i = k + 1; i < size; i++)
    		{
    			window.erase(window.find(nums[i - k - 1]));
    
    			int curValue = nums[i];
    			if (window.find(curValue) != window.end())
    				return true;
    			auto up = window.upper_bound(curValue); ***// curValue will be inserted into some interval, compare its right and left side***
    			if (up != window.end() && *up - curValue <= t)
    				return true;
    			if (up != window.begin())
    			{
    				--up;
    				if (curValue - *up <= t)
    					return true;
    			}
    
    			window.insert(curValue);
    		}
    
    		return false;
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.