桶排序原理的进阶

问题

描述

给指定n个无序的数列，要求输出这n个数排序好相邻两个差最大值；（时间复杂度要求O（logn））

输入

n(表示数列的长度，即n个数)，接下来一行n个无序的数

输出

排好序后相邻两个数之差的最大值

思路

找出n数列的范围（即最大值与最小值），设置n+1个桶，存放这些数；将数列范围分成（n+1）份，平均分给n+1个桶，然后遍历数列将每个数存放在该数所在的范围的桶中（优化：每个桶只存放该范围内最大的数和最小的数）；最后因为是n个数，然后存在n+1个桶中，必然会至少有一个空桶，有因为每个桶存数范围差一样，所以只差最大的两个数必定在空桶数最多的两侧非空桶中；差最大的为空桶数最多的右侧相邻非空桶的最小值与最左侧非空桶的最大值之差！

Code

public class MaxSub_sort {

    public static void main(String[] args) {
        Scanner as=new Scanner(System.in);
        int n=as.nextInt(),i,min = 0,max=0,r,x = 0,t=0;
        double k;
        int[] a=new int[n];
        for(i=0;i<n;i++) { 
            a[i]=as.nextInt(); 
            if(i==0) { 
                min=a[0];
                max=a[0]; 
            }else { 
                if(min>a[i]) {
                    min=a[i];
                }
                if(max<a[i]) {
                    max=a[i];
                }
            }
        }
//        System.out.println("max:"+max+",min:"+min);
        int[][] b=new int[n+1][3];
        k=(max-min+1)/(n+1.0);
//        System.out.println("k:"+k);
        for(i=0;i<n;i++) { 
            r=(int) ((a[i]-min)/k); 
         // System.out.println(r); 
            if(b[r][2]==0) { 
                b[r][0]=a[i]; 
                b[r][1]=a[i]; 
                b[r][2]=-1; 
            }else { 
                if(b[r][0]>a[i]) {
                    b[r][0]=a[i];
                }
                if(b[r][1]<a[i]) {
                    b[r][1]=a[i];
                }
            }
        }
//        for(i=0;i<=n;i++) {
//            System.out.println(i+":min="+b[i][0]+",max="+b[i][1]+";"+b[i][2]);
//        }
        int max1[]=new int[2];
        for(i=0;i<=n;i++) { 
            if(b[i][2]==0) { 
                if(t==0) { 
                    x=1;
                    t=1; 
                }else { 
                    x++; 
                    if(x>max1[0]) {
                        max1[0]=x;
                        max1[1]=i+1;
                    }
                    if(x==max1[0]) {
                        if((b[max1[1]][0]-b[max1[1]-max1[0]+1][1])<(b[i][0]-b[i-x+1][1])) {
                            max1[0]=x;
                            max1[1]=i+1;
                        }
                    }
                }
            }else {
                t=0;
            }
        }
        System.out.println(b[max1[1]][0]-b[max1[1]-max1[0]-1][1]);
//        System.out.println(max1[0]+","+max1[1]);
//        System.out.println(b[max1[1]][0]+","+b[max1[1]-max1[0]-1][1]);

    }

}

解析

• 输入时读取最大值与最小值，求出数列范围与并平均分给（n+1）个桶，给每个桶确定范围，初始默认每个桶为空；
• 遍历数列，将每个数存放在对应范围的桶中；存放时判断桶是否为空，为空时（改变通道状态为不为空），并将当前数赋值给桶中的最大值最小值；不为空时将当前数与桶中最大值最小值做比较，比最大值大，则将该桶的最大值改为当前数，比最小值小则将该桶最小值改为当前数；
• 最后遍历这（n+1）个桶，找出连续空桶最多的序号，并将连续空桶最多的右边相邻非空桶的最小值减去左边相邻非空桶的最大值就为输出的答案。