Bucket sort, C++ solution


  • 0
    Z
    class Solution {
    public:
        int maximumGap(vector<int>& nums) {
            if (nums.size() < 2) return 0;
            int min_num = nums[0], max_num = nums[0];
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] < min_num)
                    min_num = nums[i];
                if (nums[i] > max_num)
                    max_num = nums[i];
            }
            int bucket_size = (max_num - min_num) / (nums.size() - 1);
            int ans = bucket_size;
            if (bucket_size == 0) ++bucket_size;
            map<int, int> bucket_largest;
            map<int, int> bucket_smallest;
            int bucket_index;
            for (int i = 0; i < nums.size(); ++i) {
                bucket_index = nums[i] / bucket_size;
                if (bucket_largest.find(bucket_index) != bucket_largest.end()) {
                    if (bucket_largest[bucket_index] < nums[i])
                        bucket_largest[bucket_index] = nums[i];
                    if (bucket_smallest[bucket_index] > nums[i])
                        bucket_smallest[bucket_index] = nums[i];
                }
                else {
                    bucket_largest[bucket_index] = nums[i];
                    bucket_smallest[bucket_index] = nums[i];
                }
            }
            int last_largest = bucket_largest[min_num / bucket_size];
            for (int i = min_num / bucket_size + 1; i <= max_num / bucket_size; ++i) {
                if (bucket_smallest.find(i) != bucket_smallest.end()) {
                    ans = max(ans, bucket_smallest[i] - last_largest);
                    last_largest = bucket_largest[i];
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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