164. 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.

选用基数排序和计数排序的方法

基数排序

介绍线性时间排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if(nums.size() < 2) return 0;

        int n = nums.size();
        vector<int> aux(n, 0);
        int exp = 1;
        //基数排序的时候每一位上只会出现0 ~ 9
        int num = 10;

        int big = nums[0];

        for(auto &m:nums)
            big = max(big, m);

        while(big /exp){
            vector<int> count_of(num, 0);

            for(int i =0; i < n; i++)
                count_of[nums[i]/exp % 10]++;

            for(int i = 1; i < num; i++)
                count_of[i] += count_of[i - 1];

            /*for(int i = 0; i < n; i++){
                aux[count_of[nums[i]/exp % 10] - 1] = nums[i];
                count_of[nums[i]/exp % 10]--;
            }*/

            for(int i = n - 1; i >= 0; i--){
                aux[count_of[nums[i]/exp % 10] - 1] = nums[i];
                count_of[nums[i]/exp%10]--;
            }

            for(int i = 0; i < n; i++)
                nums[i] = aux[i];

            exp *= 10;
        }

        int ret = 0;
        for(int i = 1; i < n; i++)
            ret = max(ret, aux[i] - aux[ i - 1]);

        return ret;
    }
};