Maximum Gap——桶排序

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.

代码一（简单易懂版）：

桶排序，由于num中的数字肯定在[min,max]区间内，所以根据抽屉原理，假设num中有n个数字，则最大的gap必然要大于dis=(max- min)/(n-1)，所以我们可以把num所在的范围分成等间隔的区间，相邻区间内的元素之间的最大差值，即为要寻找的gap。

 class Solution {

  public:

      int maximumGap(vector<int> &num) {

          int n = num.size();

          if (n < ) return ;

          if (n == ) return abs(num[] - num[]);

          int imin = num[], imax = num[];

          for (int i = ; i < n; ++i) {

              imin = min(imin, num[i]);

             imax = max(imax, num[i]);

         }

         int dist = (imax-imin) / n + ;

         vector<vector<int> > bucket((imax-imin)/dist + );

         int idx;

         for (int i = ; i < n; ++i) {

             idx = (num[i] - imin) / dist;

             if (bucket[idx].empty()) {

                 bucket[idx].push_back(num[i]);

                 bucket[idx].push_back(num[i]);

             } else {

                 bucket[idx][] = min(bucket[idx][], num[i]);

                 bucket[idx][] = max(bucket[idx][], num[i]);

             }

         }

         int gap = , pre = , tmp;

         for (int i = ; i < bucket.size(); ++i) {

             if (bucket[i].empty()) continue;

             tmp = bucket[i][] - bucket[pre][];

             gap = max(gap, tmp);

             pre = i;

         }

         return gap;

     }

 };

代码二（刚开始我看的一直是这个，代码风格虽然很好，但是不好理解）：

这里要用到桶排序，感觉不太感兴趣，就直接看了网上的做法。

（ps:后来才知道，桶排序是基数排序的基础）

C++中vector中的一些常用函数：

取容器中的最大最小值min_element(),max_element()。

当有必要对一个接受pair参数的函数传递两个值时， make_pair()尤其显得方便。

int minAll = *min_element(nums.begin(), nums.end());

int maxAll = *max_element(nums.begin(), nums.end());

vector<pair<int, int> > buckets(bucketCount, make_pair(INT_MIN, INT_MAX));

应用桶排序的思想，把数组元素归到桶中。在一个桶内，元素差小于等于block.max-block.min。在两桶之间，元素差等于block2.min-block1.max。 
// 用桶排序

 // 算出相邻两个桶之间的最大差值

 // 如果是平均分布，则桶的数目和元素的数目相同时，其排序的时间复杂度是0(n)

 // 我们假设桶的个数和元素的数目相同，若是平均分布，则每个桶里有一个数，而若某个桶里有两个以上的桶时，这时必有至少一个是空桶，那么最大间隔可能就落在空桶的相邻两个桶存储的数之间，最大间隔不会落在同一个桶的数里，因此我们不需要对每个桶再排一次序，只需要记录同一个桶的最大值和最小值，算出前一个有最大值的桶和后一个有最小值的桶之差，则可能是最大间隔

 //步骤：1.算好用的桶的个数，用最大元素和最小元素算出平均间隔，记录在平均间隔上的最大值和最小值，

 // 2. 再算出前一个间隔里的最大值和后一个间隔里的最小值之差，取最大的一个，

 // 3. 再算出最小值和第二小的差（平均间隔最小值第一个），最大值和第二大（平均间隔最大值最后一个）的差，三个值相比，取最大的，就是最大间隔

class Solution {

public:

    int maximumGap(vector<int>& nums) {

         if (num.size() < ) return ;

        // 1. 算出用的桶数：取平均间隔，再用最大值和最小值之差除以间隔，得到桶数

        // 因为假设所有值都是平均分布的时候，如此取桶数可得时间复杂度是0(n)

        auto maxVal = *max_element(num.begin(), num.end());

        auto minVal = *min_element(num.begin(), num.end());

        int agGap = ceil((double)(maxVal - minVal) / (num.size()-)); // 平均间隔

        int bucketCount = ceil((double)(maxVal - minVal) / agGap);

        // 2. 记录每个桶的最大值和最小值

        vector<pair<int, int> > buckets(bucketCount, make_pair(INT_MIN, INT_MAX)); // 初始化桶

        for (auto val : num){

            if (val == maxVal || val == minVal) continue;

            int bucketNum = (val - minVal) / agGap;

            if (val > buckets[bucketNum].first)

                buckets[bucketNum].first = val; // 存储最大值

            if (val < buckets[bucketNum].second) buckets[bucketNum].second = val; // 存储最小值

        }

        // 3. 算出最大间隔

        int maxGap(), lastMax(minVal);

        for (auto bucket : buckets){

            if (bucket.first == INT_MIN) continue; // 空桶

            int curMax(bucket.first), curMin(bucket.second);

            maxGap = max(maxGap, curMin - lastMax);

            lastMax = curMax;

        }

        maxGap = max(maxGap, maxVal - lastMax);

        return maxGap;

    }

};

巴特西

Maximum Gap——桶排序

最新文章

热门文章