leetcode Maximum Gap

曾经终败给现在 2022-08-05 01:24 163阅读 0赞

# 题目 #

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.  
题目来源：[https://leetcode.com/problems/maximum-gap/][https_leetcode.com_problems_maximum-gap]

# 分析 #

一个没有排序的数组，返回排好序后的相邻之间元素的最大间隔。  
苦思冥想想不出来，参考了一下网上的的做法（[参考链接][Link 1]），自己慢慢消化吧。使用若干个桶存放所有元素，使得最大的gap位于两个桶之间（前面桶的最小值和随后桶的最大值之差）。这样的话，桶的数目该是多少位宜呢？平均分割元素区间（max\_elm - min\_elm），每个区间的大小是一个avg\_gap。这样的话，如果所有元素平均分布，则每个桶里一个元素，退化为排序。如果不平均分布，则必然有的桶为空，有的桶里面的元素多于1个。最大的gap也就不可能出现在一个桶里面，求不同桶之间的gap就行了。

![这里写图片描述][20150529210641246]

# 代码 #

class Solution {
    public:
        int maximumGap(vector<int>& nums) {
            int len = nums.size();
            if(len < 2)
                return 0;
            //find max element
            int max_num = *max_element(nums.begin(), nums.end());
            //find min element
            int min_num = *min_element(nums.begin(), nums.end());
            //average gap, ceil(0.3) = 1
            int avg_gap = ceil((double)(max_num - min_num)/(len - 1));
            int bucket_num = ceil((double)(max_num - min_num) / avg_gap);
            //buckets.first is max element in this bucket, initialized by the min integer(0x80000000)
            //buckets.second is min element in this bucket, initialized by the max integer(0x7fffffff)
            vector<pair<int, int> >buckets(bucket_num, make_pair(0x80000000, 0x7fffffff));
            for(auto val : nums){
                if(val == max_num || val == min_num)
                    continue;
                int i = (val - min_num) / avg_gap;//find the correct bucket
                if(val > buckets[i].first)
                    buckets[i].first = val;
                if(val < buckets[i].second)
                    buckets[i].second = val;
            }
            int max_gap = 0;
            int last_max = min_num;
            for(auto bucket : buckets){
                if(bucket.first == 0x80000000)//empty bucket
                    continue;
                int cur_max = bucket.first;
                int cur_min = bucket.second;
                max_gap = max(max_gap, cur_min - last_max);
                last_max = cur_max;
            }
            max_gap = max(max_gap, max_num - last_max);
            return max_gap;
        }
    };

[https_leetcode.com_problems_maximum-gap]: https://leetcode.com/problems/maximum-gap/
[Link 1]: http://www.cnblogs.com/ganganloveu/p/4162290.html%20%E2%80%9C%E9%93%BE%E6%8E%A5%E2%80%9D
[20150529210641246]: /images/20220805/de3272bbc3d44b889a2cac20d2f56a98.png