桶排序思想与高频面试题---相邻两数最大插值(maxGap)

2019/05/13 21:30
阅读数 34

高频面试题:

clip_image002

比如:3 1 6 2 7

排序后是:

clip_image004

这道题目借用了桶这个概念,但是没有进行桶排序

N个数准备N+1个桶

clip_image006

中间的数字:把min到max范围等分成N+1份,一个数属于哪号范围,就放到哪个桶里

例如:

clip_image008

排序之后的相邻数字可能在同一个桶,也可能在相邻的桶

clip_image010

15的相邻值,可能来自于11(同一个桶),可能来自于21(相邻桶)

N个数,准备N+1个桶,min放进第0个桶,max放进第N个桶,中间必有一个空桶

clip_image012

空桶边非空桶的max值,与空桶边非空桶的min值相邻,且min–max一定大于每个桶所表示的范围【比如一个桶表示10~19,那桶表示的范围是10,这两个值相减一定大于10】

所以在寻找最大差值的时候,不需要考虑同一个桶中的数据,最大差值一定来自于不同桶(前一个桶的max和后一个桶的min)

每个桶不需要统计桶中的所有数,只需要统计桶中的min和max;当然还需要统计一个boolean类型的数据,这个桶里是否为空

(1) 有数字进入某个桶,桶的boolean类型的变量就要从false变为true

(2) 如果是第一次进入桶,那min = max = 这个数

(3) 如果某个数字再次进入了某个桶,就更新这个桶中的min 和max

(4) 然后从1号桶开始(因为0号桶一定非空),如果是空的,跳到下一个桶,如果是非空的,找前一个非空桶。对于每一个非空桶,都找它前一个非空桶的max和当前这个桶的min

(5) min–max记录最大差值

(6) 要求的最大差值一定在其中是最大的,用一个全局变量就可以找到它

提问:为什么不是找那个空桶,计算空桶两侧的非空桶的min–max

答:如下面的情况,最大差值是19;我们提出这个空桶的概念是否定最大差值来自同一个桶

clip_image014

clip_image016

每个桶的三种信息(是否为空、min、max)用三个数组来描述

clip_image018

import java.util.Arrays;

public class MaxGap {

    public static void main(String[] args) {
        int[] arr ={0,2,15,23,21,67,88,4,99};//答案44
//        int[] arr ={1,2,3,6,7};//答案3
        System.out.println(maxGap(arr));
        
    }
    
    public static int maxGap(int[] arr){
        if (arr.length<2 || arr == null) {
            return 0;
        }
        //1.遍历找到数组中的最小值min最大值max
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]<min) {
                min = arr[i];
            }
            if (arr[i]>max) {
                max = arr[i];
            }
        }
        System.out.println("min = "+min+" max = "+max);
        //2.如果数组中是一串相同的数字,差值为0
        if (max == min) {
            return 0;
        }
        //3.构造3个桶
        int len = arr.length;
        boolean[] hasNum = new boolean[len+1];//数组中的默认值是false
        int[] mins = new int[len+1];
        int[] maxs = new int[len+1];
        //4.重新遍历这个数组,找到每个桶中的max、min
        for (int i = 0; i < arr.length; i++) {
            //看数组中的每一个数字属于几号桶
            int bucketNumber = bucket(arr[i], max, min, len);
            System.out.println("第"+i+"个数字在第"+bucketNumber+"号桶");
            //桶中无数据
            if (!hasNum[bucketNumber]) {
                mins[bucketNumber] = arr[i];
                maxs[bucketNumber] = arr[i];
                hasNum[bucketNumber] = true;
            }else {//桶中有数据
                mins[bucketNumber] = Math.min(arr[i], mins[bucketNumber]);
                maxs[bucketNumber] = Math.max(arr[i], maxs[bucketNumber]);
            }
            
        }
        System.out.println("每个桶中的最小值mins"+Arrays.toString(mins));
        System.out.println("每个桶中的最大值maxs"+Arrays.toString(maxs));
        System.out.println(Arrays.toString(hasNum));
        
        //找当前桶的min和前一个非空桶的max
        int maxGap = 0;
        int lastMax = maxs[0];//前一个非空桶的max
        for(int i=1; i<hasNum.length; i++){
            if (hasNum[i]) {
                maxGap = Math.max((mins[i] - lastMax), maxGap);
                System.out.println("第"+i+"次最大值为 "+ maxGap);
//                if (lastMax - mins[i] > maxGap) {
//                    maxGap = lastMax - mins[i];
//                }
                lastMax = maxs[i];
            }
        }
        return maxGap;
    }
    /**
     * 判断一个数字属于几号桶
     * @param num  被判断的数字
     * @param max    数组中的最大值
     * @param min   数组中的最小值
     * @param n     数组中的数据量N
     */
    public static int bucket(int num, int max, int min,int n){
        return (int)(num-min)*(n+1)/(max-min+1);
    }

}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部