思路:题目要求在线性时间复杂度和空间复杂度的条件下解决问题,所以在排序时我们要选择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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/596673.html