LeetCode[Sort]: 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.

从Discuss上借鉴了这个桶排序（Bucket sort）的算法：https://oj.leetcode.com/discuss/18499/bucket-sort-java-solution-with-explanation-o-time-and-space

思路是这样的：数组中有N个元素，最小的元素为min，最大的元素为max，那么最大的间距将不小于ceil((max-min)/(N-1))。（其中，ceil(x)指的是不小于x的最小整数）。假设平均间距为gap=ceil((max-min)/(N-1))，把所有的元素放进N-1个桶里，第k(0<=k<=N-2)个桶里放所有位于区间[min+k*gap, min+(k+1)*gap)内的元素。因此除了最大的元素max和最小的元素min，其余的N-2个元素都被放进这N-1个桶里，，因此至少有一个桶是空的，我们只需要存储每个桶里最大的元素和最小的元素就可以算出最大的间距是多少。

C++代码实现如下：

int maximumGap(vector<int> &num) {if (num.empty() || num.size() == 1) return 0;int min = num[0], max = num[0];for (auto n : num) {if (n < min) min = n;if (n > max) max = n;}int gap = (max – min – 1) / (num.size() – 1) + 1;vector<int> bucketMins(num.size() – 1, INT_MAX);vector<int> bucketMaxs(num.size() – 1, INT_MIN);for (auto n : num) {if (n != min && n != max) {int bucketIdx = (n – min) / gap;if (n < bucketMins[bucketIdx]) bucketMins[bucketIdx] = n;if (n > bucketMaxs[bucketIdx]) bucketMaxs[bucketIdx] = n;}}int maxGap = INT_MIN, prev = min;for (int i = 0; i < num.size() – 1; ++i) {if (bucketMins[i] == INT_MAX && bucketMaxs[i] == INT_MIN) continue;if (bucketMins[i] – prev > maxGap) maxGap = bucketMins[i] – prev;prev = bucketMaxs[i];}return std::max(max – prev, maxGap);}

时间性能如下：

只要有信心，人永远不会挫败