排序:164、最大间距
程序员文章站
2022-06-16 20:56:12
思路:题目要求在线性时间复杂度和空间复杂度的条件下解决问题,所以在排序时我们要选择O(n)的时间复杂度,如基数排序,桶排序。1、基数排序:将所有待比较正整数统一为同样的数位长度,数位较短的数前面补零。然后,从个位开始进行基数为10的计数排序,一直到最高位计数排序完后,数列就变成一个有序序列(利用了计数排序的稳定性)。class Solution {public: int maximumGap(vector& nums) { int n=n.....
思路:题目要求在线性时间复杂度和空间复杂度的条件下解决问题,所以在排序时我们要选择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