专栏首页算法修养LeetCode 164. Maximum Gap (排序)

LeetCode 164. Maximum Gap (排序)

题目

题意:就是给你一个数组,让你输出排好序后,相邻元素差值最大的那个差值。

题解:首先,当然我们可以用快排,排完序之后,遍历一遍数组,就能得到答案了。但是快速排序的效率是O(n* logn),不是题目要求的线性效率,也就是O(n)的效率。

那么诸多排序算法中,也是由线性效率的排序算法,当然这些算法的目标是线性效率,而在实际情况中的效率也并不是最快的。首先就是基数排序,基数排序的效率是O(n*k),

k 是由元素的位数决定的。

线性时间的排序还有一个桶排序,桶排序,一开始选择一些桶,每个桶代表一个范围区间,把数字按部就班放到桶里,然后在桶里再继续排序,(可以继续递归用桶排序,也可以用别的排序)。

在这道题目中,桶排序是最好的选择,因为如果使用桶排序,则无需将整个数组都排序,题目要求的是排好序之后的相邻元素的最大差值。

假设最小值是min,最大值是max,数组的个数是n。那么假设这n个数字在min和max之间平均分布, k = (min-max)/(n-1) 代表相邻元素之间的差值。现在假设n个数字不是平均分布的,就是任意哪种情况,那么相邻元素之间的差值永远都是大于K的,这是可以证明的。所以确定了min,max,n,那么相邻元素的最大差值都是必定大于等于k的。

所以我们的每个桶的大小(区间范围)设为k,这样答案就在桶和桶之间,而不存在桶里,所以我们在第一次按部就班的放到桶里之后,直接比较桶之间差值,就能得出答案了。

效率是O(n+t), t就是桶的数量,(max-min)/k+1

基数排序

class Solution {
public:
    vector<int> a[10];
    vector<int> b[10];
    int maximumGap(vector<int>& nums) {
        
        
        int n = nums.size();
        if(n<2)
            return 0;
        int m=0;         
        for(int i=0;i<n;i++)
        {
            m=max(m,MaxBit(nums[i]));
        }
        
        for(int i=0;i<m;i++)
        {
            if(i==0)
            {
                for(int j=0;j<n;j++)
                {
                    int x=Bit(nums[j],i);
                
                    a[x].push_back(nums[j]);
                }
            }
            else
            {
                for(int j=0;j<10;j++)
                {
                    for(int k=0;k<b[j].size();k++)
                    {
                        int x=Bit(b[j][k],i);
                        
                        a[x].push_back(b[j][k]);
                    }
                }
            }
            
            
             for(int j=0;j<10;j++)
             {
                b[j].clear();
                for(int k=0;k<a[j].size();k++)
                {
                    b[j].push_back(a[j][k]);
                }
                a[j].clear();
             }
           
        }
        
        
        int ans=0;
        
        int l=-1;
        for(int i=0;i<10;i++)
        {
            for(int j=0;j<b[i].size();j++)
            {
                if(l==-1)
                {
                    l=b[i][j];
                    continue;
                }
                
                ans=max(ans,b[i][j]-l);
                
                l=b[i][j];
            }
        }
        
        return ans;
        
    }
    
    int Bit(int x,int pos)
    {
        while(pos)
        {
            x/=10;
            pos--;
        }
        
        return x%=10;
    }
    
    
    int MaxBit(int x)
    {
        int ax=0;
        while(x)
        {
            ax++;
            x/=10;
        }
        
        return ax;
    }
    
    
};

桶排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        
        if(nums.size()<2)
            return 0;
        
        int m = nums[0];
        int n = nums[0];
        
        int len = nums.size();
        
        for(int i=1;i<nums.size();i++)
        {
            m = max(m,nums[i]);
            n = min(n,nums[i]);
        }
        
        int t = max(1,(m-n)/(len-1));
        
        int num = (m-n) / t + 1;
        int a[num];
        int b[num];
        
        memset(a,-1,sizeof(a));
        memset(b,-1,sizeof(b));
        for(int i=0;i<nums.size();i++)
        {
            int index = (nums[i]-n)/t;
           
            if(a[index]==-1)
                a[index]=nums[i];
            else
                a[index]=min(a[index],nums[i]);
            
            if(b[index]==-1)
                b[index]=nums[i];
            else
                b[index]=max(b[index],nums[i]);
        }
        
        int ans=0;
        int l=-1,r=-1;
        for(int i=0;i<num;i++)
        {
            if(a[i]!=-1)
            {
               r=a[i];
               if(l!=-1)
                   ans=max(ans,r-l);
              
               l=b[i];
                
            }
        
        }
        
        return ans;
      
    }    
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • LeetCode 1632. Rank Transform of a Matrix

    思路是贪心,将所有的元素从小到大排序。并且维护两个数组,一个数组代表每一行的当前已经填上的最大的rank,比如nrank[0]=2 表示第0行,目前已经填到了r...

    ShenduCC
  • LeetCode Contest 180

    ShenduCC
  • 挑战程序竞赛系列(28):3.5最小费用流

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 次小生成树

    次小生成树 次小生成树 我们已经熟知了求最小生成树的方法,用kruskal,prim算法都可以搞 那么我们如何求次小生成树呢? 这里次小生成树的定义是 边...

    attack
  • 09:向量点积计算

    09:向量点积计算 总时间限制: 1000ms 内存限制: 65536kB描述 在线性代数、计算几何中,向量点积是一种十分重要的运算。 给定两个n维向量a=(...

    attack
  • 第K小数 uva 10041 - Vito's Family poj 2388 Who's in the Middle

    很容易理解题目的意思,就是求某个点到其他点的距离之和,而且要让这个和最小,很明显是求中位数了。

    xindoo
  • light oj 1255 - Substring Frequency (KMP)

    裸裸的KMP,参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。

    xindoo
  • 力扣(LeetCode)刷题,简单+中等题(第30期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿
  • 力扣(LeetCode)刷题,简单题(第27期)

    力扣(LeetCode)定期刷题,每期10道题,业务繁重的同志可以看看我分享的思路,不是最高效解决方案,只求互相提升。

    不脱发的程序猿

扫码关注云+社区

领取腾讯云代金券