【leetcode】Maximum Gap

时间:2021-05-04 04:38:11

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;
}
};