My code:
public class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
radixSort(nums);
int max = Integer.MIN_VALUE;
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i] - nums[i - 1]);
}
return max;
}
private void radixSort(int[] nums) {
int max = getMax(nums);
for (int digit = 1; digit <= max; digit *= 10) {
countingSort(nums, digit);
}
}
private int getMax(int[] nums) {
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
return max;
}
private void countingSort(int[] nums, int digit) {
int[] ct = new int[10];
for (int i = 0; i < nums.length; i++) {
ct[(nums[i] / digit) % 10]++;
}
for (int i = 1; i < 10; i++) {
ct[i] += ct[i - 1];
}
int[] temp = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
temp[ct[(nums[i] / digit) % 10] - 1] = nums[i];
ct[(nums[i] / digit) % 10]--;
}
for (int i = 0; i < nums.length; i++) {
nums[i] = temp[i];
}
}
}
看到这道题目，第一个想法是排序。然后要求排序时间复杂度是 O(n)
就想到了 radix sort
但是忘记了是什么原理了，幸好以前总结了。温故了一下。
reference:
http://www.jianshu.com/p/d461a3f69499
code reference：
https://discuss.leetcode.com/topic/22221/radix-sort-solution-in-java-with-explanation/2
time complexity: O(n)
worst time complexity: O(10 * n) Integer.MAX_VALUE 一共十位
space complexity: O(n)
Anyway, Good luck, Richardo! -- 09/28/2016
