I finally got AC in C++


  • 27
    C

    Using a set container to keep the k+1-length array,which all elements are distinct.Before the container's size reached k+1, we just find the first element that is not less than [nums[i]-t] and judge the element's value whether it is less than [nums[i]+t]. Starting to move forward by erasing the head and adding element at the backend after the container's size reached k+1. The existence of the first element ,which is not less than [nums[i]-t] and less than [nums[i]+t], is the prerequisite of existing other eligible elements.

     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
        {
        		if (!k || t<0 || nums.size()<2)
            		return false;
            	set<int>record;                   
            	auto nLen = nums.size();
            	for (int i = 0; i < nLen;++i)
            	{
            		if (i>k)
            			record.erase(nums[i - k - 1]);         
            		set<int>::iterator lower = record.lower_bound(nums[i] - t);
            		if (lower != record.end() && abs(nums[i] - *lower) <= t)
            			return true;
            
            		record.insert(nums[i]);
            	}
            	return false;
        }

  • 0
    W
    This post is deleted!

  • -1
    Q

    i am wondering you use the STL Container set,which can only fill with distinct number; if the same number insert into your variable record, it will only store one, and the erase will remove the only one; but intact there is one left in the record???


  • 0
    W

    use multiset is better


  • 0
    A

    multiset is not necessary since that value appeared multiple times is not useful anymore


  • 0
    W

    right, duplicates will not affect the result.

    the difference for duplicates are 0, must be fulfilled with the 't'


  • 0
    A
    This post is deleted!

  • 0
    Y

    what if the nums vector contains element like INT_MIN and t >= 1, will record.lower_bound(nums[i] - t) overflow?


  • 0
    R

    I wonder still why set works here? I think removing duplicates can easily goes wrong.


  • 0
    S

    i dont understand neither


  • 0
    P

    weibest is right, the difference of duplicates are 0


  • 0
    8

    I am kind of confused about this solution. Could you explain a little bit how this solution work for case like [5, 2, 1], 2, 1 ? I thought your solution will return false in this case, but it's actually true.


  • 0
    R

    Remember set is ordered. So after the first two number are inserted, the elements in the set is {2, 5}. Now you look at the 3rd number, it's 1 and record.lower_bound(1) returns the iterator to 2. If you don't know why it returns the tierator to 2, you need to reference to the manual of set:)


Log in to reply
 

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