排序：164、最大间距

思路：题目要求在线性时间复杂度和空间复杂度的条件下解决问题，所以在排序时我们要选择O(n)的时间复杂度，如基数排序，桶排序。

1、基数排序：将所有待比较正整数统一为同样的数位长度，数位较短的数前面补零。然后，从个位开始进行基数为10的计数排序，一直到最高位计数排序完后，数列就变成一个有序序列（利用了计数排序的稳定性）。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return 0;
        int div=1;
        vector<int>temp(n);
        //找到最大值
        int maxVal=*max_element(nums.begin(),nums.end());
        while(div<=maxVal){
            vector<int>cnt(10);
            //依次求个位、十位、百位...的基数个数
            for(int i=0;i<n;i++){
                int digit=(nums[i]/div)%10;
                cnt[digit]++;
            }
            //相当于对求得的基数个数进行从小到大排序
            for(int i=1;i<10;i++){
                cnt[i]+=cnt[i-1];
            }
            //根据基数的排序来对原数组排序
            for(int i=n-1;i>=0;i--){
                int digit=(nums[i]/div)%10;
                temp[cnt[digit]-1]=nums[i];
                cnt[digit]--;
            }
            //将一次排序后的数组替代原数组
            copy(temp.begin(),temp.end(),nums.begin());
            //基数依次为个位、十位、百位...
            div*=10;
        }
        int res=0;
        for(int i=1;i<n;i++){
            res=max(res,nums[i]-nums[i-1]);
        }
        return res;
    }
};

2、桶排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return 0;
        int minVal=*min_element(nums.begin(),nums.end());
        int maxVal=*max_element(nums.begin(),nums.end());
        //每个桶之间的距离
        int d=max(1,(maxVal-minVal)/(n-1));
        //桶数量
        int bucketSize=(maxVal-minVal)/d+1;
        //每个桶里面存储该桶中的最小值，最大值
        vector<pair<int,int>>bucket(bucketSize,{-1,-1});
        for(int i=0;i<n;i++){
            //数组中元素位于哪一个桶
            int idx=(nums[i]-minVal)/d;
            //更新桶中最小值，最大值
            if(bucket[idx].first==-1){
                bucket[idx].first=bucket[idx].second=nums[i];
            }else{
                bucket[idx].first=min(bucket[idx].first,nums[i]);
                bucket[idx].second=max(bucket[idx].second,nums[i]);
            }
        }
        int res=0;
        int prev=-1;
        //求得最大距离
        for(int i=0;i<bucket.size();i++){
            if(bucket[i].first==-1) continue;
            if(prev!=-1){
                res=max(res,bucket[i].first-bucket[prev].second);
            }
            prev=i;
        }
        return res;
    }
};

 

本文地址：https://blog.csdn.net/carolineme/article/details/110171373