Leetcode 164 Maximum Gap 桶排序好题
Leetcode 164 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
给定数组，找出数组排序后两个相邻数字的差的最大值是多少。
难点在于要求线性时间和空间复杂度完成。
不加这个要求，直接快排就可以了，加了这个要求怎么办呢？我也想了很久......
想了好久，看了题解，发现还是思维僵化，根本就没有想到桶排序。
引用官方题解中的话
Suppose there are N elements and they range from A to B. Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)] Let the length of a bucket to be len = ceiling[(B - A) / (N - 1)], then we will have at most num = (B - A) / len + 1 of bucket
当所有元素均匀分布的时候，相邻数字的差的最大值最小，因此可以构造桶大小的为[(B - A) / (N - 1)]，
同一个桶内的元素的差一定小于桶的大小，这样就不需要管桶内的大小关系了，只需要关注每个桶的最小值和前一个非空桶的最大值之差就可以了。
class Solution {
public:
int maximumGap(vector<int>& nums) {
if(nums.size()<2) return 0;
int minn = INT_MAX;
int maxx = INT_MIN;
for(int i = 0; i<nums.size(); i++)
{
minn = min(minn, nums[i]);
maxx = max(maxx, nums[i]);
}
double len = (maxx - minn)*1.0 / (nums.size() - 1);
if(len == 0) return 0;//防止所有元素一样大
int cnt = floor((maxx - minn) / len + 1);
vector<int> minb(cnt, INT_MAX);
vector<int> maxb(cnt, INT_MIN);
for(int i = 0;i<nums.size();i++) //元素分入桶
{
int id = floor((nums[i] - minn) / len);
minb[id] = min(minb[id], nums[i]);
maxb[id] = max(maxb[id], nums[i]);
}
int res = 0, premax = maxb[0];//第一个桶包含最小值，因此一定不为空
for(int i = 1;i<cnt; i++)
{
if(minb[i] != INT_MAX)
{
res = max(res, minb[i] - premax);
premax = maxb[i];
}
}
return res;
}
};