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.
解法一：
先排序O(nlogn)，再一次遍历，得到maxGap
虽然不满足O(n)的时间要求，但是最直观的想法。
class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.empty() || nums.size() == )
return ;
sort(nums.begin(), nums.end());
int ret = ;
for(int i = ; i < nums.size(); i ++)
ret = max(ret, nums[i]-nums[i-]);
return ret;
}
};
解法二：为了满足O(n)复杂度，我尝试了计数排序，但是会TLE。因此使用桶排序来做。
(计数排序可以看做是桶大小为1的桶排序，但由于桶数目太多导致遍历时间过长。)
最大gap肯定是出现在后一个有效桶的min与前一个有效桶的max之间。
“有效”指的是忽略空桶。
class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.empty() || nums.size() == )
return ;
int n = nums.size();
int minAll = *min_element(nums.begin(), nums.end());
int maxAll = *max_element(nums.begin(), nums.end());
// type conversion!!!
double gap = ((double)(maxAll - minAll)) / (n - );
// compute min and max element for each bucket
vector<int> minV(n-, INT_MAX);
vector<int> maxV(n-, INT_MIN);
for(int i = ; i < n; i ++)
{
if(nums[i] != maxAll)
{// the bktId of maxAll will fall out of bucket range
int bktId = (int)((nums[i]-minAll)/gap);
minV[bktId] = min(minV[bktId], nums[i]);
maxV[bktId] = max(maxV[bktId], nums[i]);
}
}
int ret = ;
int curMax = maxV[];
for(int i = ; i < n-; i ++)
{
if(minV[i] != INT_MAX)
{
ret = max(ret, minV[i]-curMax);
curMax = maxV[i];
}
}
ret = max(ret, maxAll-curMax);
return ret;
}
};