下面的分桶个数做的不太好，原来的解法是用的
int gap = (big - small) / vlen;
if (gap == 0) {
gap = 1;
}
下面是现在的Java解法：
package com.company;
import java.util.*;
class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) {
return 0;
}
// 用 Radix 排序
int small = Integer.MAX_VALUE;
int big = 0;
for (int num : nums) {
if (num < small) {
small = num;
}
if (num > big) {
big = num;
}
}
System.out.println("big is " + big + " small " + small);
int gap = (big - small - 1) / (nums.length - 1) + 1;
if (gap == 0) {
return 0;
}
int gap_num = (big - small) / gap + 1;
int[] first = new int[gap_num];
int[] second = new int[gap_num];
// [ )
System.out.println("gap is " + gap + " len is " + nums.length + "big is " + big + " small " + small);
for (int num : nums) {
int index = (num - small) / gap;
if (first[index] == 0 || num < first[index]) {
first[index] = num;
}
if (second[index] == 0 || num > second[index]) {
second[index] = num;
}
}
int ret = -1;
int last = -1;
for (int i=0; i<gap_num; i++) {
if (first[i] == 0) {
continue;
}
if (last == -1) {
last = second[i];
ret = last - first[i];
}
else {
if (first[i] - last > ret) {
ret = first[i] - last;
}
if (second[i] - first[i] > ret) {
ret = second[i] - first[i];
}
last = second[i];
}
}
return ret;
}
}
public class Main {
public static void main(String[] args) {
System.out.println("Hello!");
Solution solution = new Solution();
int[] nums = {1,1,1,1,1,5,5,5,5,5};
int ret = solution.maximumGap(nums);
System.out.printf("Get ret: %s\n", ret);
/*Iterator<List<Integer>> iterator = ret.iterator();
while (iterator.hasNext()) {
Iterator iter = iterator.next().iterator();
while (iter.hasNext()) {
System.out.printf("%d,", iter.next());
}
System.out.println();
}*/
System.out.println();
}
}