康瑞部落

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.

解题思路：

1、最传统的思路，先给数组排序，然后遍历数组，找到最大的差值。这种方法时间复杂度为O(nlogn)，空间复杂度为O(1)，不满足题目要求。

2、我想到了set会自动给元素排序，逐一插入set数组，然后遍历set中的元素，求出最大差值。后来查资料发现，set元素的插入、查找操作的时间复杂度为O(logn)，总时间复杂度为O(nlogn)，不符合题目要求。

3、因为给出的是正整数，因此可以考虑基数排序。基数排序的时间复杂度为O(k*n)，k是一个小整数，空间复杂度为O(n)，因此满足要求。代码如下：

class Solution {
public:
	int maximumGap(vector<int> &num) {
		int count = num.size();
		if (count < 2){
			return 0;
		}
		int max = num[0];
		int min = num[0];
		for (int i = 1; i<count; i++){
			max = max > num[i] ? max : num[i];
			min = min > num[i] ? num[i] : min;
		}
		if (max == min){
			return 0;
		}
		int maxLen = getNumberLength(max);
		//基数排序
		int base = 1;   //n位
		vector<int> bucket[10];
		for (int i = 0; i< maxLen; i++){
			for (int j = 0; j < count; j++){
				bucket[getSpecialPostionNumber(num[j], base)].push_back(num[j]);
			}
			num.clear();
			for (int j = 0; j < 10; j++){
				for (int k = 0; k < bucket[j].size(); k++){
					num.push_back(bucket[j][k]);
				}
				bucket[j].clear();
			}
			base *= 10;
		}

		int maxGap = 0;

		for (int i = 1; i < count; i++){
			maxGap = maxGap > num[i] - num[i - 1] ? maxGap : num[i] - num[i - 1];
		}

		return maxGap;
	}
private:
	//获得特定位上的数字，i表示1位，10位等
	int getSpecialPostionNumber(int num, int i){
		return (num / i) % 10;
	}
	//获得数字的长度
	int getNumberLength(int num){
		int len = 0;
		while (num != 0){
			len++;
			num /= 10;
		}
		return len;
	}
};

4、官方给出的办法类似于桶排序。它也符合负数的情况（若有负数，需要考虑溢出的情况）。大体思想为;

假设有N个元素A到B。
那么最大差值不会小于ceiling[(B - A) / (N - 1)]（均匀差时最大差值最小）
令bucket（桶）的大小len = ceiling[(B - A) / (N - 1)]，则最多会有(B - A) / len + 1个桶
对于数组中的任意整数K，很容易通过算式loc = (K - A) / len找出其桶的位置，然后维护每一个桶的最大值和最小值
由于同一个桶内的元素之间的差值至多为len - 1，因此最终答案不会从同一个桶中选择。
对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。

代码如下：

class Solution {
public:
    int maximumGap(vector<int> &num) {
       if (num.size() < 2) return 0;
        //遍历一遍，找出最大最小值
        int maxNum = num[0];
        int minNum = num[0];
        for (int i : num) {
            maxNum=max(maxNum,i);
            minNum=min(minNum,i);
        }
        // 每个桶的长度len,向上取整所以加+
        int len = (maxNum - minNum) / num.size() + 1;
        
        //桶的个数:(maxNum - minNum) / len + 1,每个桶里面存储属于该桶的最大值和最小值即可，注意这里的最大最小值是局部的
        vector<vector<int>> buckets((maxNum - minNum) / len + 1);
        for (int x : num) {
            int i = (x - minNum) / len;
            if (buckets[i].empty()) {
                buckets[i].reserve(2);
                buckets[i].push_back(x);
                buckets[i].push_back(x);
            } else {
                if (x < buckets[i][0]) buckets[i][0] = x;
                if (x > buckets[i][1]) buckets[i][1] = x;
            }
        }
        //gap的计算，For each non-empty buckets p, find the next non-empty buckets q, return min（ q.min - p.max ）
        int gap = 0;
        int prev = 0;
        for (int i = 1; i < buckets.size(); i++) {
            if (buckets[i].empty()) continue;
            gap = max(gap, buckets[i][0] - buckets[prev][1]);
            prev = i;
        }
        return gap;
    }
};