最大间隔数-桶排序应用


www.srblog.cn

问题

给定一个未排序的数组,返回其排序后的数组中相邻元素之差的最大值
例:给定数组:[5,9,8,3,15]
   排序后:[3,5,8,9,15]
相邻元素之差最大的是15-9=6,结果即为6。
要求:时间空间复杂度均为O(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public class MaximumGap {

public static int maximumGap(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int len = arr.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, arr[i]);
max = Math.max(max, arr[i]);
}
if (min == max) {
return 0;
}
boolean book[] = new boolean[len + 1];
int maxs[] = new int[len + 1];
int mins[] = new int[len + 1];
int id = 0;
for (int i = 0; i < len; i++) {
// 划分桶号
id = (int) ((arr[i] - min) * len / (max - min));
mins[id] = book[id] ? Math.min(mins[id], arr[i]) : arr[i];
maxs[id] = book[id] ? Math.max(maxs[id], arr[i]) : arr[i];
book[id] = true;
}
int res = 0;
// 第一个桶内默认是最小值
int lastMax = maxs[0];
int i = 1;
for (; i <= len; i++) {
if (book[i]) {
// 两个相邻的非空桶,后一个的最小值减去前一个的最大值为相对间隔最大值
res = Math.max(res, mins[i] - lastMax);
// 当前桶的最大值更新为前一个最大值
lastMax = maxs[i];
}
}
return res;

}

public static int comparator(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
Arrays.sort(arr);
int gap = Integer.MIN_VALUE;
for (int i = 1; i < arr.length; i++) {
gap = Math.max(arr[i] - arr[i - 1], gap);
}
return gap;
}

public static int[] getRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
// 获取 -maxVlaue + 1 ~ maxValue 的值
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}

return arr;

}

public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] book = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
book[i] = arr[i];
}
return book;
}

public static void main(String[] args) {
// 测试次数
int test = 50000;

// 数组长度
int maxSize = 100;

// 最大数值
int maxValue = 100;

boolean flag = true;

for (int i = 0; i < test; i++) {
int arr1[] = getRandomArray(maxSize, maxValue);
// 拷贝比较
int arr2[] = copyArray(arr1);
if (maximumGap(arr1) != comparator(arr2)) {
flag = false;
break;
}

}
System.out.println(flag ? "测试正常" : "发生错误");
// 随机测试一组数据
int arr[] = getRandomArray(maxSize, maxValue);
int t = maximumGap(arr);
System.out.println("原数组:"+Arrays.toString(arr));
Arrays.sort(arr);
System.out.println("排序后:"+Arrays.toString(arr));
System.out.println("最大差值:"+t);
}
}
sr wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
0%