[C++] A dummy AC solution


  • 0
    Y

    I didn't know this problem can be perfectly solved by bucket search. Following is my AC solution which greedily either solve this problem in O(nt) or O(nk)

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (k<t) return nkalgo(nums, k, t); 
            else return ntalgo(nums, k, t);
        }
        bool nkalgo(vector<int>& nums, int k, int t) {
            // O(nk) method
            for (int offset=1;offset<=k;offset++) {
                for (int i=0;i<nums.size()-offset;i++) {
                    long long temp= abs(((long long)nums[i])-((long long)nums[i+offset]));
                    if (temp<=(long long)t) return true;
                }
            }
            return false;
        }
        
        bool ntalgo(vector<int>& nums, int k, int t) {
            // O(nt) method
            unordered_map<int,vector<int>> idxs;
            for (int i=0;i<nums.size();i++) {
                idxs[nums[i]].push_back(i);
            }
            
            for (auto it=idxs.begin();it!=idxs.end();it++) {
                int val=it->first; // value now
                for (int diff=-t;diff<=t;diff++) {
                    if ((diff>0&&val>=INT_MAX-diff)||(diff<0&&val<=INT_MIN-diff)) continue;
                    
                    if (idxs.count(val+diff)>0) { // exist another matched number -> start comparing idxs
                        for (int i=0;i<it->second.size();i++) {
                            for (int j=0;j<idxs[val+diff].size();j++) {
                                int idxDiff=abs(it->second[i]-idxs[val+diff][j]);
                                if (idxDiff>0&&idxDiff<=k) return true;
                            }
                        }
                    }
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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