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.
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size(), mini, maxi, i, j, k, prev = -, ans = ;
if(n < )
return ;
mini = maxi = nums[];
for(i = ; i < n; i++)
{
if(nums[i] < mini)
mini = nums[i];
if(nums[i] > maxi)
maxi = nums[i];
}
k = (maxi - mini) / n + ;
vector<vector<int>> v(n);
for(i = ; i < n; i++)
{
j = (nums[i] - mini) / k;
if( == v[j].size())
{
v[j].push_back(nums[i]);
v[j].push_back(nums[i]);
}
else
{
v[j][] = max(nums[i], v[j][]);
v[j][] = min(nums[i], v[j][]);
}
}
for(i = ; i < n; i++)
{
if( == v[i].size())
continue;
if(prev != -)
{
j = v[i][] - v[prev][];
ans = max(ans, j);
}
prev = i;
}
return ans;
}
};
将nums分为n组，每组k = (maxi - mini) / n + 1个数，分别求出每组的最大值和最小值。