LeetCode164—最大间距

排序

第一次提交的代码：（快速排序）

class Solution 
{
    public int maximumGap(int[] nums) 
    {
        int n=nums.length,ans=0;
        Arrays.sort(nums);//Arrays.sort()给数组升序排序的内置函数
        for(int i=0;i<n-1;i++)
            if(nums[i+1]-nums[i]>ans) ans=nums[i+1]-nums[i];
        return ans;
    }
}

第二次提交的代码：（桶）

class Solution 
{
    public int maximumGap(int[] nums) 
    {
        int n=nums.length;
        if(n<2) return 0;
        int Max=-1,Min=Integer.MAX_VALUE,ans=0;
        for(int i=0;i<n;i++)
        {
            Max=Math.max(Max,nums[i]);
            Min=Math.min(Min,nums[i]);
        }
        int[] Tmin=new int[n+1];//保存每个桶内数字的最小值
        Arrays.fill(Tmin,Integer.MAX_VALUE);//Arrays.fill可以把数组内每个元素置为同一指定值
        int[] Tmax=new int[n+1];//保存每个桶内数字的最大值
        Arrays.fill(Tmax,-1);
        int gap=(Max-Min)/n+1;//指每个桶内包含数字的最大范围，+1为防止gap=0
        for(int i=0;i<n;i++)
        {
            int id=(nums[i]-Min)/gap;
            Tmax[id]=Math.max(Tmax[id],nums[i]);
            Tmin[id]=Math.min(Tmin[id],nums[i]);
        }
        int pre=Min;
        for(int i=0;i<=n;i++)
        {
            if(Tmax[i]==-1) continue;
            ans=Math.max(ans,Tmin[i]-pre);//相邻桶之差中取最大值
            pre=Tmax[i];//pre保存上一个桶的最大值
        }
        return ans;
    }
}

第三次提交的代码：（基数排序）

class Solution 
{
    public int maximumGap(int[] nums) 
    {
        int n=nums.length;
        if(n<2) return 0;
        int Max=-1,ans=0,exp=1;
        List<ArrayList<Integer>> list=new ArrayList<>();
        for(int i=0;i<10;i++) list.add(new ArrayList<>());//嵌套List的初始化
        for(int i=0;i<n;i++) Max=Math.max(Max,nums[i]);
        while(Max>=exp)//完全是基数排序思想的模拟实现
        {
            for(int i=0;i<10;i++) list.set(i,new ArrayList<>());//set修改第i位上List的值
            for(int i=0;i<n;i++) list.get(nums[i]/exp%10).add(nums[i]);//get读取第i位上的值
            int id=0;
            for(int i=0;i<10;i++)
                for(int j=0;j<list.get(i).size();j++)
                    nums[id++]=list.get(i).get(j);
            exp*=10;
            if(exp<=0) break;//防止exp溢出后变为负数，导致死循环
        }
        for(int i=0;i<n-1;i++)
            ans=Math.max(ans,nums[i+1]-nums[i]);
        return ans;
    }
}