O(n) C++ using buckets with explanation


  • 0
    Z

    Reference: https://discuss.leetcode.com/topic/19991/o-n-python-using-buckets-with-explanation-10-lines

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            map<int, int> buckets;
            int offset = (t > 0)? 1: 0;
            for (int i = 0; i < nums.size(); ++i) {
                int bucket_index = (t > 0)? nums[i] / t: nums[i];
                for (int index = bucket_index - offset; index <= bucket_index + offset; ++index) {
                    if (buckets.find(index) != buckets.end() && abs((long long)buckets[index] - (long long)nums[i]) <= t) {
                        return true;
                    }
                }
                buckets[bucket_index] = nums[i];
                if (buckets.size() > k) {
                    buckets.erase((t > 0)? nums[i - k] / t: nums[i - k]);
                }
            }
            return false;
        }
    };
    

Log in to reply
 

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