[LeetCode]Maximum Gap

直接sort的话我们可以得到O(n * log n)的解法，但是题目要求我们给出O(n)的解法。那么基于比较的sort方法我们肯定不能用了，因为下界是O(n * log n)。我们就得考虑counting sort或者bucket sort之类O(n)的解法。首先我们可以想到Radix sort，radix sort是对每一位用counting sort来排序，之后得到所有数的排序。从低位到高位，从高到低都可以，假设最大的数有d为，总共n个数，那么排序的时间复杂度是O(d * n)。空间复杂度O(n + d)，代码如下：

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size() < 2)return 0;
	int maxNum = *max_element(nums.begin(), nums.end()), div = 1, base = 10, len = nums.size();
	while(maxNum / div)
	{
	vector<int> count(base, 0);
	for(int i = 0; i < len; ++i)
	{
	int digit = (nums[i] / div) % base;
	++count[digit];
	}
	for(int i = 1; i < base; ++i)
	count[i] += count[i - 1];
	vector<int> aux(len);
	for(int i = len - 1; i >= 0; --i)
	{
	int digit = (nums[i] / div) % base;
	aux[--count[digit]] = nums[i];
	}
	for(int i = 0; i < len; ++i)
	nums[i] = aux[i];
	div *= 10;
	}
	int res = 0;
	for(int i = 1; i < len; ++i)
	res = max(res, nums[i] - nums[i - 1]);
	return res;
	}
	};

view raw Maximum Gap_1.cpp hosted with ❤ by GitHub

Bucket sort我们也可以考虑，但是显然我们不能简单地将bucket size设为1，因为假设最大数和最小数相差很多的时候，是很费空间并且不效率的。具体我们可以参考这篇文章，简单来说，假设一组数量为n的数中最大数为max，最小数为min，那么maximum gap的最小值就为g = (max - min) / (n - 1)。因为假设所有数为等差数列，那么每个数的差就正好为g，那么任意移动任意一数，将其增加或者减小，就只会增加maximum gap的值。所以我们就将bucket size设为g，那么我们就有(max - min) / g + 1 = n个bucket，鉴于maximum gap的值永远>= g，我们只需要比较每一个bucket的最大值和下一个bucket的最小值即可。时间复杂度O(n)，空间复杂度O(n)，代码如下：

	struct Bucket
	{
	bool used;
	int maxNum, minNum;
	Bucket()
	{
	used = false;
	maxNum = INT_MIN;
	minNum = INT_MAX;
	}
	};
	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size() < 2)return 0;
	int maxNum = *max_element(nums.begin(), nums.end()), minNum = *min_element(nums.begin(), nums.end());
	int len = nums.size(), bucketSize = max(1, (maxNum - minNum) / (len - 1)), bucketNum = (maxNum - minNum) / bucketSize + 1;
	vector<Bucket> buckets(bucketNum);
	for(auto& num : nums)
	{
	int bIndex = (num - minNum) / bucketSize;
	buckets[bIndex].used = true;
	buckets[bIndex].maxNum = max(num, buckets[bIndex].maxNum);
	buckets[bIndex].minNum = min(num, buckets[bIndex].minNum);
	}
	int maxGap = 0, prevBucket = INT_MAX;
	for(auto& bucket : buckets)
	{
	if(!bucket.used)continue;
	maxGap = max(bucket.minNum - prevBucket, maxGap);
	prevBucket = bucket.maxNum;
	}
	return maxGap;
	}
	};

view raw Maximum Gap_2.cpp hosted with ❤ by GitHub