地址

https://leetcode.com/problems/maximum-gap/

题目

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

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

  • You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
  • Try to solve it in linear time/space.

思路

基于比较的排序算法复杂度是O(NlogN)，这是已经被证明了的。所以能做到O(N)排序的算法只有以下不基于比较的：计数排序，基数排序，桶排序。这三种算法在某些特定情况下可以O(N)排序。计数排序需要O(K=max-min)的空间，这题元素范围在int内，现在不可行。那就只有基数排序和桶排序可以用了。

  • 基数排序

    按十进制的位数为关键字 ，从低位向高位 分别进行基数排序（中间排序的过程必须是稳定排序，不然会打乱全面排序好的结果）。

  • 桶排序

    将元素划分到m个桶内，则每个桶内约有(max-min)/m个元素。对于每个桶内元素进行排序后，然后将m个桶内的元素依次输出即是排序后的结果。

    但这题有一个巧妙的做法，我们直接划分成n-1个桶：

    1. 假设这n-1个桶中都有至少一个元素，则有必有一个桶中有两个元素。此时原问题的答案就是max（相邻两个桶中元素的间隔，桶内两个元素（如果有两个元素的话）的间隔）。
    2. 假设这n-1个 桶中有一个桶是空的，则 必有一个桶中有三个及以上 的元素，此时因为每个桶内的数的范围是gap=(max-min)/(n-1)。设第i个桶是空的，则 第i个桶的前面第一个有元素的桶和后一个第一个 有元素的桶之间的间隔必然大雨gap=(max-min)/(n-1)。对于包含三个元素及以上的 桶，其桶内元素间隔必然小于gap=(max-min)/(n-1)。所以对于含有多个元素的桶，我们只需要记录桶中元素的最小值和最大值即可。

    综合 以上两点，可以发现最大的间隔值=max（相邻桶之间的间隔，同一个桶内最小与最大元素 的间隔）。

代码

class Solution {
public:
    int maximumGap(vector<int>& a) {
        int n=a.size();
        if(n<2) return 0;
        int mx = a[0], mi = a[0];
        for(auto &x: a)
            mx=max(mx, x), mi=min(mi,x);
        int dis=max((mx-mi+1)/(n-1), 1);
        vector<int>bk[50000+7];
        for(auto &x: a)
        {
            int idx = (x-mi)/dis;
            if(bk[idx].size()==0)
                bk[idx].push_back(x), bk[idx].push_back(x);
            else
                bk[idx][0]=min(x,bk[idx][0]), bk[idx][1]=max(x,bk[idx][1]);
        }
        int ans=0,pre=mi;
        for(int i=0;i<n;i++)
        if(!bk[i].empty())
        {
            //cout<<i<<" "<<pre<<" "<<bk[i][0]<<" "<<bk[i][1]<<" "<<ans<<endl;
            ans=max(ans, bk[i][1]-bk[i][0]);
            ans=max(ans, bk[i][0]-pre);
            pre=bk[i][1];
        }
        return ans;
    }
};