【leetcode】 Maximum Gap

地址

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:

1
2
3
4
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:

1
2
3
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(相邻桶之间的间隔,同一个桶内最小与最大元素 的间隔)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}
};