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          */
24         
25         //第一步，找出这一组数的最大值与最小值之差
26         int min = A[0];
27         int max = A[0];
28         for(int i=0; i<A.length; i++){
29             if(A[i] < min) min = A[i];
30             if(A[i] > max) max = A[i];
31         }
32         
33         //第二步：根据差值开辟合适的桶(桶的数量为数组的长度+1，桶的数量大于数组的长度,中间有空桶)
34         //第三步：将每个数放入到对应的桶中，中间会有空桶的情况
35         boolean[] hasNum = new boolean[A.length+1];//判断桶中是否有数
36         int[] maxNumBucket = new int[A.length+1];//记录当前桶的最大值
37         int[] minNumBucket = new int[A.length+1];//记录当前桶的最小值
38         for(int i=0; i<A.length; i++){
39             int 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         }
44         
45         //第四步：只需要循环遍历桶，比较后一个桶中最小值与前一个桶中最大值之差，找出差值最大的即为所求
46         int result = 0;//最终的结果
47         int leftBucketMax = maxNumBucket[0];//0号桶肯定有值
48         int rightBucketMin = 0;
49         int startBucket = 1;//从1号桶开始进行遍历
50         
51         for(int i=startBucket; i<A.length+1; i++){
52             if(!hasNum[i]) continue;
53             rightBucketMin = minNumBucket[i];
54             if(rightBucketMin - leftBucketMax > result)
55                 result = rightBucketMin - leftBucketMax;
56             leftBucketMax = maxNumBucket[i];
57         }
58         
59         return result;
60     }
61     public int 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          */
68         return (int)((num-min)/((max-min)*1.0/arrLength));      
69     }
70     @Test
71     public void test(){
72         int[] arr = new int[]{3,7,19,6,4};
73         System.out.println(maxGap(arr,5));
74     }
75 }