題目

LeetCode中文站

解答

根據(jù)題意我們就可以直到這是一題先排序，然后再尋找最大間距的題目，我們先使用最簡單的解法試試。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        int maxGap = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i++) {
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        }
        return maxGap;
    }
};

以上代碼時間復(fù)雜度為，空間復(fù)雜度我們可以默認他為快速排序為。

現(xiàn)在就來繼續(xù)優(yōu)化上面的代碼，之前我們在零基礎(chǔ)學(xué)排序中學(xué)到，還有三種線性的時間復(fù)雜度的排序算法，桶排序、基數(shù)排序、計數(shù)排序，三種排序的應(yīng)用場景有限。
但是在題目中提到你可以假設(shè)數(shù)組中所有元素都是非負整數(shù)，且數(shù)值在 32 位有符號整數(shù)范圍內(nèi)。，所以根據(jù)這個條件，我們使用桶排序和基數(shù)排序是都合理的。

桶排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        // 先找出最大和最小值
        int minNum = nums.front();
        int maxNum = nums.front();
        for (int i = 0; i < nums.size(); i++) {
            minNum = min(minNum, nums[i]);
            maxNum = max(maxNum, nums[i]);
        }
        
        // 先確定桶大小
        int bucketSize = max(1, (maxNum - minNum) / ((int)nums.size() - 1));
        int bucketCount = ceil((maxNum - minNum + 1) / (float)bucketSize);
        vector<vector<int>> bucket(bucketCount);
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == maxNum) {
                bucket.back().push_back(nums[i]);
                continue;
            }
            // 看數(shù)據(jù)是在n哪個桶中的
            int bucketIndex = (nums[i] - minNum) / bucketSize;
            bucket[bucketIndex].push_back(nums[i]);
        }
    
        nums.resize(0);
        for (int i = 0; i < bucket.size(); i++) {
            // 計算大小
            if (!bucket[i].empty()) {
                sort(bucket[i].begin(), bucket[i].end());
                nums.insert(nums.end(), bucket[i].begin(), bucket[i].end());
            }
        }
        
        int maxGap = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i++) {
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        }
        return maxGap;
    }
};

以上代碼的時間復(fù)雜度為，空間復(fù)雜度為。

基數(shù)排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        // 先找出最大
        int maxNum = nums.front();
        for (int i = 0; i < nums.size(); i++) {
            maxNum = max(maxNum, nums[i]);
        }
        
        // 計算位數(shù)
        int bit = 0;
        while (1) {
            if (maxNum >= pow(10, bit)) {
                bit++;
            } else {
                break;
            }
        }
        
        
        for (int i = 0; i < bit; i++) {
            vector<vector<int>> bucket(10);
            // 從最低位開始排序
            for (auto subNum : nums) {
                int bitNum = int(subNum / pow(10, i)) % 10;
                bucket[bitNum].push_back(subNum);
            }
            // 重新放入桶中
            nums.resize(0);
            for (auto ve : bucket) {
                nums.insert(nums.end(), ve.begin(), ve.end());
            }
        }

        int maxGap = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        }
        return maxGap;
    }
};

以上代碼的時間復(fù)雜度為，空間復(fù)雜度為。

當(dāng)我AC的時候我發(fā)現(xiàn)了一個排名第一的答案，這個AC解很奇怪，他直接跳過了排序的步驟，通過桶的概念，把最大最小值存在來，最后通過比較找到了最大間距。這個解法我感覺我很厲害，但是我還沒有找到一種很好的解釋，所以我就先放著，希望知道的朋友可以告訴我一下，這個解法的原理是什么？

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if(nums.size() < 2) {
            return 0;
        }
        int minval = INT_MAX;
        int maxval = INT_MIN;
        for(auto subnum : nums) {
            minval = min(subnum, minval);
            maxval = max(subnum, maxval);
        }
        
        int bucketSize = max(1, (maxval - minval) / ((int)nums.size() - 1));
        int bucketNum = (maxval - minval) / bucketSize;
        
        vector<int> bucketsMin(bucketNum, INT_MAX);
        vector<int> bucketsMax(bucketNum, INT_MIN);
        
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == maxval || nums[i] == minval) {
                continue;
            }
            int index = (nums[i] - minval) / bucketSize;
            bucketsMin[index] = min(bucketsMin[index], nums[i]);
            bucketsMax[index] = max(bucketsMax[index], nums[i]);
        }
        int maxGap = 0;
        int pre = minval;
        for(int i = 0; i < bucketNum; i++) {
            if(bucketsMin[i] == INT_MAX || bucketsMax[i] == INT_MIN) {
                continue;
            }
            maxGap = max(maxGap, bucketsMin[i] - pre);
            pre = bucketsMax[i];
        }
        maxGap = max(maxGap, maxval - pre);
        return maxGap;
    }
};

以上代碼的時間復(fù)雜度為，空間復(fù)雜度為。