欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排序:164、最大间距

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

排序: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

相关标签: leetcode刷题