Solutions using sort or set in C++, still one question bothers me


  • 2

    Solutions

    This problem is quite classic recently, so here we are trying to shed some light on it and provide some basic solutions to it.

    Sort

    Basic idea for this is to sorting the array first while maintaining the indexes along with the numbers, so we are to use pair to simplify this in C++, after which everything else is just so intuitive here. The whole solution in C++ is as follows.

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) 
    {
    	vector<pair<long, int>> withIndex;
    	for(int i = 0; i < nums.size(); ++i) withIndex.emplace_back(nums[i], i);
    	sort(withIndex.begin(), withIndex.end(), [](const pair<long, int>& a, const pair<long, int>&b) { return a.first<b.first; });
    	for(int i = 0; i < nums.size(); ++i)
    	{
    		int j = i+1;
    		while(j < nums.size())
    		{
    			if(withIndex[j].first-withIndex[i].first > t) break;
    			if(abs(withIndex[j].second-withIndex[i].second) <= k) return true;
    			j++;
    		}
    	}
    	return false;
    }
    

    Set

    Since there is a range we have to keep to search for the valid numbers, so directly we can use sliding window to maintain that feature. As for searching in that window, we should avoid the array or list which will require us to search one by one, which is linear time cost. So as a result we can take advantage of built-in set which can retrieve the range for us in logn instead of n.

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) 
    {
    	if(k <= 0) return false;
    	if(t < 0) return false;
    	int size = nums.size();
    	set<int> k_set;
    	for(int i = 0; i < size; ++i)
    	{
    		if(i > k) k_set.erase(nums[i-k-1]);
    		auto iter = k_set.lower_bound(nums[i]-t);
    		if(iter!=k_set.end() && *iter<=(long)nums[i]+t) return true;
    		k_set.insert(nums[i]);
    	}
    	return false;
    }
    

    Notes:

    1. the first two statements are just used for avoiding futile searching which is actually unnecessary;
    2. when replacing the k_set.lower_bound with lower_bound(k_set.begin(), k_set.end()) the solution just got TLE; lower_bound though has the feature to locate but it's using linear time cost actually on set instead of logn.

  • 0

    After checking the STL, I found out the following facts:

    • built-in lower_bound is directly adopting the feature of the binary search tree to locate the result which will be O(logn)
    • lower_bound function itself working on set will cost linear time O(n), for its binary search is based on advance(current, mid) which is used to move the iterator one step at a time

    So as a result, here if we use lower_bound(set.begin(), set.end()) instead of set.lower_bound() we are actually have a very bad performance ever worse than direct array itself.


  • 0
    A

    @LHearen The sort is actually not very helpful. The time complexity is roughly O(nlogn + nt).
    Even without the sort, we can still compare every element with its next k neighbors, which results in a time complexity of about O(n*k). So the sort is actually redundant. Am I right?


  • 0

    @ayuanx Yeah, you are right about this. What I was thinking about was the O(nt) is smaller than O(nk). As you mentioned, it's actually could be another problem to balance them. Your point is right. Thank you!


Log in to reply
 

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