c++ solution using bucket, beats 99.6%


  • 3
    M

    Inspired by @maruchan76 https://discuss.leetcode.com/topic/29477/why-no-one-posted-o-n-solution-in-c-using-bucket-sort, but use a array (buckets) to store the indices of numbers in vector "nums" without using unordered_map. Use type long long to prevent overflow.

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if (k < 1 || t < 0) return false;
            int min_num = INT_MAX;
            int max_num = INT_MIN;
            for (auto& num: nums) {
                min_num = std::min(min_num, num);
                max_num = std::max(max_num, num);
            }
            long long bucket_width = static_cast<long long>(t) + 1;
            int size = (static_cast<long long>(max_num) - static_cast<long long>(min_num)) / bucket_width + 1;
            int* bucket = new int[size];
            memset(bucket, -1, sizeof(int) * size);
            for (int i = 0; i < nums.size(); i++) {
                int bucket_idx = (static_cast<long long>(nums[i])-min_num) / bucket_width;
                if (bucket[bucket_idx] >= 0)
                    return true;
                bucket[bucket_idx] = i;
                if (bucket_idx >= 1) {
                    int j = bucket[bucket_idx-1];
                    if (j >= 0 && abs(static_cast<long long>(nums[i]) - nums[j]) <= t)
                        return true;
                }
                if (bucket_idx < size-1) {
                    int l = bucket[bucket_idx+1];
                    if (l >= 0 && abs(static_cast<long long>(nums[i]) - nums[l]) <= t)
                        return true;
                }
                if (i >= k) {
                    bucket[(nums[i-k] - min_num) / bucket_width] = -1;
                }
            }
            return false;
        }
    };
    

  • 0
    Q

    Don't know why nobody votes this. This definitely the fastest C++ solution.


  • 0

    Here's java version. cpp type casting is awesome, while java's :-(

    I'm impressed by your code static_cast<long long>(t) + 1, and the type casting is just precise.

    Well there's an edge case that can't be handle by the Java. If the min = Integer.MIN_VALUE, max = Integer.MAX_VALUE; and t = 1, size will still overflow, which will be 2^31 instead of 2^31-1.

    Another reason is that in Java, only int type can be used to index on an array, so the size can't be long type. array size limit. However, CPP has no hard limitation on the array size.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (k < 1 || t < 0)
                return false;
    
            long range;
            long max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int num : nums) {
                max = max > num ? max : num;
                min = min < num ? min : num;
            }
            range = max - min + 1;
            long bucket_with = ((long) t) + 1;
            int size = (int) (range / bucket_with + 1);
            int[] buckets = new int[size];
            Arrays.fill(buckets, -1);
    
            for (int i = 0; i < nums.length; i++) {
                int bucket_idx = (int) ((((long) nums[i]) - min + 1) / bucket_with );
                if (buckets[bucket_idx] >= 0) {
                    return true;
                }
                buckets[bucket_idx] = i;
                
                if (bucket_idx > 0) {
                    int j = buckets[bucket_idx-1];
                    if (j >= 0 && Math.abs(((long) nums[i]) - nums[j]) <= t) {
                        return true;
                    }
                }
                
                if (bucket_idx < size-1) {
                    int j = buckets[bucket_idx + 1];
                    if (j >= 0 && Math.abs(((long) nums[i]) - nums[j]) <= t) {
                        return true;
                    }
                }
                
                if (i >= k) {
                    buckets[(int) ((((long) nums[i-k]) - min + 1) / bucket_with )] = -1;
                }
            }
            
            return false;
        }
    

Log in to reply
 

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