Finally AC, C++ 16ms using map, O(nlogn) with explanation


  • 0
    1. Using a map to store the numbers, takes O(nlogn).
      key(nums[i]) - value(index), value is a vector<int> since duplicate numbers can have multiple indices.
    2. If array contains duplicate numbers and the absolute difference between their indices <=k, return true.
    3. Since map is already sorted, we only need to check the interval(map[i], map[i+t]), which could be seen as constant time O(1) depends on t and array itself.
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            map<int,vector<int>>m;
            for(int i=0;i<nums.size();i++) m[nums[i]].push_back(i);
            for(map<int,vector<int>>::iterator it1=m.begin();it1!=m.end();it1++){
                if(it1->second.size()>1 && minDiff(it1->second)<=k && t>=0) return true; 
                map<int,vector<int>>::iterator it2=it1;
                it2++;
                for(;it2!=m.end();it2++){
                    int diff=it2->first-it1->first;
                    if(diff>t) break;
                    if(it2->first>0 && it1->first<0 && diff<it2->first) continue; //check overflow
                    if(it2->first<0 && it1->first>0 && diff>0) continue; //check overflow
                    if(diff<=t && minDiff(it1->second,it2->second)<=k) return true;
                }
            }
            return false;
        }
        
        int minDiff(vector<int>& v1, vector<int>& v2){
            int minD=INT_MAX;
            for(int i=0;i<v1.size();i++)
                for(int j=0;j<v2.size();j++) minD=min(minD,abs(v1[i]-v2[j]));
            return minD;
        }
        
        int minDiff(vector<int>& v){
            int minD=INT_MAX;
            for(int i=0;i<v.size();i++)
                for(int j=i+1;j<v.size();j++) minD=min(minD,abs(v[i]-v[j]));
            return minD;
        }
    

Log in to reply
 

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