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.
Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.
如果不考虑题目中要求的Linear time/space，实际上只需要先sort，然后找到最大的就可以了。
class Solution {
public:
int maximumGap(vector<int> &num) {
if(num.size()<)
return ;
sort(num.begin(),num.end());
int max=;
for(int i=;i<num.size()-;i++)
{
if(num[i+]-num[i]>max)
max=num[i+]-num[i];
}
return max;
}
};
符合题意的方法：
由于num中的数字肯定在[min,max]区间内，所以根据抽屉原理，假设num中有n个数字，则最大的gap必然要大于dis=(max-min)/(n-1)，所以我们可以把num所在的范围分成等间隔的区间，相邻区间内的元素之间的最大差值，即为要寻找的gap
class Solution {
public:
int maximumGap(vector<int> &num) {
if(num.size()<) return ;
if(num.size()==) return abs(num[]-num[]);
int n=num.size();
int min,max,i;
min=max=num[];
for(i=;i<num.size();i++)
{
if(min>num[i]) min=num[i];
if(max<num[i]) max=num[i];
}
// 找到区间间隔
//注意此处，也可以写成(max-min)/n+1,此时就不需要num.size()==2的边界条件了
int dis=(max-min)/(n-)+;
vector<vector<int> > bucket((max-min)/dis+);
for(i=;i<n;i++)
{
int x=num[i];
int index=(x-min)/dis;
//把元素放入不同的区间中
if(bucket[index].empty())
{
bucket[index].reserve();
bucket[index].push_back(x);
bucket[index].push_back(x);
}
else
{
if(bucket[index][]>x) bucket[index][]=x;
if(bucket[index][]<x) bucket[index][]=x;
}
}
int pre=;
int gap=;
//在相邻的区间中（区间内有元素的相邻区间）寻找最大的gap
for(i=;i<bucket.size();i++)
{
if(bucket[i].empty()) continue;
int tmp=bucket[i][]-bucket[pre][];
if(gap<tmp) gap=tmp;
pre=i;
}
return gap;
}
};