c/c++语言开发共享排序：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;     } };

c/c++开发分享排序：164、最大间距地址：https://blog.csdn.net/carolineme/article/details/110171373