LeetCode[Sort]: Maximum Gap

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 &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 bucketMins(num.size() - 1, INT_MAX);
        vector 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);
    }

時間性能如下：