算法--相邻两数最大差值

                         1
                        package
                         com.hzf.sort;

                         2
                         3
                        import
                         org.junit.Test;

                         4
                         5
                        /**
                         6
                         * 有一个整形数组A，请设计一个复杂度为O(n)的算法，算出排序后相邻两数的最大差值。

                         7
                         * 

                         8
                         * 给定一个int数组A和A的大小n，请返回最大的差值。保证数组元素多于1个。

                         9
                         * 

                        10
                         * 测试样例： [1,2,5,4,6],5 

                        11
                         * 返回：2

                        12
                         * 

                        13
                         * 
                        @author
                         hzf

                        14
                         *

                        15
                        */
                        16
                        public
                        class
                         Gap {

                        17
                        public
                        int maxGap(int[] A, int n) {
18/**19         * 第一步，找出这一组数的最大值与最小值之差
20         * 第二步：根据差值开辟合适的桶(桶的数量为数组的长度+1，保证入桶之后，中间有空桶)
21         * 第三步：将每个数放入到对应的桶中，中间会有空桶的情况
22         * 第四步：只需要循环遍历桶，比较后一个桶中最小值与前一个桶中最大值之差，找出差值最大的即为所求
23*/2425//第一步，找出这一组数的最大值与最小值之差26int min = A[0];
27int max = A[0];
28for(int i=0; i<A.length; i++){
29if(A[i] < min) min = A[i];
30if(A[i] > max) max = A[i];
31        }
3233//第二步：根据差值开辟合适的桶(桶的数量为数组的长度+1，桶的数量大于数组的长度,中间有空桶)
34//第三步：将每个数放入到对应的桶中，中间会有空桶的情况35boolean[] hasNum = newboolean[A.length+1];//判断桶中是否有数36int[] maxNumBucket = newint[A.length+1];//记录当前桶的最大值37int[] minNumBucket = newint[A.length+1];//记录当前桶的最小值38for(int i=0; i<A.length; i++){
39int bucketNum = bucket(A[i], A.length, min, max);//当前数应该放入哪个桶中40             maxNumBucket[bucketNum] = hasNum[bucketNum] ? Math.max(maxNumBucket[bucketNum], A[i]) : A[i];
41             minNumBucket[bucketNum] = hasNum[bucketNum] ? Math.min(minNumBucket[bucketNum], A[i]) : A[i];
42             hasNum[bucketNum] = true;
43        }
4445//第四步：只需要循环遍历桶，比较后一个桶中最小值与前一个桶中最大值之差，找出差值最大的即为所求46int result = 0;//最终的结果47int leftBucketMax = maxNumBucket[0];//0号桶肯定有值48int rightBucketMin = 0;
49int startBucket = 1;//从1号桶开始进行遍历5051for(int i=startBucket; i<A.length+1; i++){
52if(!hasNum[i]) continue;
53             rightBucketMin = minNumBucket[i];
54if(rightBucketMin - leftBucketMax > result)
55                 result = rightBucketMin - leftBucketMax;
56             leftBucketMax = maxNumBucket[i];
57        }
5859return result;
60    }
61publicint bucket(long num, long arrLength, long min, long max) {//防止两个int型的数相乘，越界62/**63         * 3,7,12,6,4
64         * 最小值3,最大值12,每个桶的范围是(12-3)/5
65         * 
66         * 假设当前值为6,那么它应放入(int)((6-3)/(9/5))桶中
67*/68return (int)((num-min)/((max-min)*1.0/arrLength));      
69    }
70    @Test
71publicvoid test(){
72int[] arr = newint[]{3,7,19,6,4};
73         System.out.println(maxGap(arr,5));
74    }
75 }