[LeetCode] Maximum Gap

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@porker2008for 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;}};

接受失败，是我们不常听到或看到的一个命题，我们大都接受的是正面的教育，