Q：给定n个实数x1,x2,...,xn,求这n个实数在实轴上相邻2个数之间的最大差值,要求设计线性的时间算法
A：
最简单的是直接用sort，然后一个一个计算gap，再找到最大，但sort函数本身是快速排序，默认时间为O(nlogn)。
有三种线性的时间复杂度的排序算法，桶排序、基数排序、计数排序，三种排序的应用场景有限。
使用桶排序：
（1）介绍桶排序
一句话总结：划分多个范围相同的区间，每个自区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
（2）桶排序解决最大间隙问题
- 找到n个数据中最大和最小数据maxx和minx；
- 用n-2个点等分区间[minx,maxx]，即将[minx,maxx]等分为n-1个区间（前闭后开区间），将这些区间看做桶，编号为1,2,...,n-2,n-1，且桶i的上界和桶i+1的下届相同，即每个桶的大小相同；
每个桶的大小为： dblAvrGap=(maxx-minx)/(n-1)
实际上，这些桶的边界就构成了一个等差数列（首项为minx，公差d=dblAvrGap），且人为将minx放入第1个桶，将maxx放入第n-1个桶。
编程实现中，用以下数据结果存放有关桶的数据：
int *count=new int[n]; //实际分到每个桶的数据个数
double *low=new double[n]; //实际分到每个桶的最小数据
double *high=new double[n]; //实际分到每个桶的最大数据 - 将n个数放入n-1个桶中：
3.1 按如下规则将x[i]分配到某个桶(编号index)中： index=int((x[i]-minx)/dblAvrGap)+1；
若x[i]=minx，则被分到第1个桶中(minx即为桶1的下界)；
若x[i]=桶j的下界(也是桶j-1的上界)，则被分到桶j中(j>=1)；
若x[i]=maxx，则被分到桶n中(max为桶n的下界桶n-1的上界)，但没有桶n，解决办法：
可人为将其移入桶n-1中或者再加一个桶，这并不影响求其最大间隙；
3.2 调整分到该桶的最大最小数据； - 求最大间隙：
除最大最小数据maxx和minx以外的n-2个数据被放入n-1个桶中，由抽屉原理可知至少有一个桶是空的；
又因每个桶的大小相同，所以最大间隙不会在同一桶中出现；
一定是某个桶的上界(dblHigh)和其后某个桶的下界(dblLow)之间隙，且该两桶之间的桶(即编号在该两桶编号之间的桶)一定是空桶；
即最大间隙在桶i的上界和桶j的下界之间产生(j>=i+1)；
代码：
public static int maximumGap(ArrayList<Integer> num) {
if (num.size() < 2)
return 0;
int maxNum = num.get(0);
int minNum = num.get(0);
for (int i = 1; i < num.size(); i++) {
maxNum = Math.max(maxNum, num.get(i));
minNum = Math.min(minNum, num.get(i));
}
//桶的长度
int len = (maxNum - minNum) / num.size() + 1;
//桶的个数
int size = (maxNum - minNum) / len + 1;
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < size; i++) {
buckets.add(new ArrayList<>());
}
for (Integer integer : num) {
int j = (integer - minNum) / len;
if (buckets.get(j).isEmpty()) {
buckets.get(j).add(integer);
} else {
//插入排序调节内部顺序。实际上该题只需要找到该桶最小和最大即可，不需要这么麻烦。用插入排序是熟悉一下这种方法
boolean flag = false;
for (int k = 0; k < buckets.get(j).size(); k++) {
if (buckets.get(j).get(k) > integer) {
buckets.get(j).add(k, integer);
flag = true;
break;
}
}
if (!flag)
buckets.get(j).add(integer);
}
}
int gap = 0;
int prev = 0;
for (int i = 1; i < buckets.size(); i++) {
if (buckets.get(i).isEmpty())
continue;
gap = Math.max(gap, buckets.get(i).get(0) - buckets.get(prev).get(1));
prev = i;
}
return gap;
}
使用基数排序
public static int maximumGap1(ArrayList<Integer> num) {
if (num.size() < 2)
return 0;
int maxNum = num.get(0);
for (Integer n : num) {
maxNum = Math.max(maxNum, n);
}
int bit = 0;
while (true) {
if (maxNum >= Math.pow(10, bit)) {
bit++;
} else
break;
}
for (int i = 0; i < bit; i++) {
ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
for (int j = 0; j < 10; j++) {
bucket.add(new ArrayList<>());
}
for (Integer n : num) {
int a = (int) (n / Math.pow(10, i));
int bitNum = a % 10;
bucket.get(bitNum).add(n);
}
num.clear();
for (ArrayList<Integer> nums : bucket) {
num.addAll(nums);
}
}
int maxGap = 0;
for (int i = 1; i < num.size(); i++) {
maxGap = Math.max(maxGap, num.get(i) - num.get(i - 1));
}
return maxGap;
}
引用：https://www.jianshu.com/p/94f08afe4ecb
https://blog.csdn.net/jiyanfeng1/article/details/39312011
https://blog.csdn.net/qq_27124771/article/details/87651495