My Accepted O(n) Solution -> simplify this problem into Contain Duplicate II


  • 1
    Y
    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (nums.size() < 2) return false;
            if (t < 0) return false;
            
            map<int, int> m1;
            map<int, int> m2;
            
            for (int i = 0; i < nums.size(); i++){
                int num1 = nums[i] >= 0 ? nums[i]/(t+1) : nums[i]/(t+1) - 1;
                if (m1.count(num1) && m1[num1] >= i - k)   return true;
                m1[num1] = i;
                
                int num2 = nums[i] >= 0 ? (nums[i] + (t+2) / 2 )/(t+1) : (nums[i] + (t+2) / 2 )/(t+1) - 1;
                if (m2.count(num2) && m2[num2] >= i - k)   return true;
                m2[num2] = i;
            }
            
            return false;
        }
    };

  • 0
    S

    It may not work for [5,7], 2, 2. In the first dictionary, we got m1[1] = 0 and m1[2] = 1 and in the second dictionary, we got m2[2] =0 and m2[3] =1

    Please tell me where I was wrong...
    Thanks!


  • 0
    Y

    Hi ! I think you are right! I think it gets around in Leetcode's testing then, it got accepted......but thank you for pointing this case out ! This is very good !!

    is there anyway we can modify this code around to make it work?


  • 0
    S

    Hi, sorry I don't know.... I think it depends on the remains after nums[i] divided by (t+1).


  • 0
    L
    class Solution {
    public:
         bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (nums.size() < 2) return false;
            if (t < 0) return false;
    
            unordered_map<int, int> m1;
            for (int i = 0; i < nums.size(); i++){
                int num1 = nums[i] >= 0 ? nums[i]/(t+1) : nums[i]/(t+1) - 1;
                if (m1.count(num1) && m1[num1] >= i - k)   return true;
                m1[num1] = i;
                if(m1.count(num1+1))
                {
                    if(labs((long)nums[i]-nums[m1[num1+1]])<=(long)t&&m1[num1+1] >= i - k)return 1;
                }
                if(m1.count(num1-1))
                {
                    if(labs((long)nums[i]-nums[m1[num1-1]])<=(long)t&&m1[num1-1] >= i - k)return 1;
                }
    
               
            }
    
            return false;
        }
    
    };

Log in to reply
 

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