LC164. Maximum Gap
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
此题排序可做。此题要求线性时间空间排序, 那也就是桶排序和基数排序了，虽然知道复杂度但是对于具体实现不是很熟。
Bucket sort 桶排序
Bucket sort works as follows:
- Set up an array of initially empty “buckets”.
- Scatter: Go over the original array, putting each object in its bucket.
- Sort each non-empty bucket.
- Gather: Visit the buckets in order and put all elements back into the original array.
Pseudocode:
function bucketSort(array, n) is
buckets ← new array of n empty lists
for i = 0 to (length(array)-1) do
insert array[i] into buckets[msbits(array[i], k)]
for i = 0 to n - 1 do
nextSort(buckets[i]);
return the concatenation of buckets[0], ...., buckets[n-1]
保证桶中元素的顺序放入和取出，桶排序是stable的。
Bucket solution:
O(n) time and O(n) space.
public class Solution {
public int maximumGap(int[] nums) {
// bucket sort, for num in nums, max_gap(which is max - min) >= (max - min)/length-1
// so let size of bucket = ceiling((max - min)/length-1)
// so number of bucket <= max_gap/size + 1(<= nums.length), which ensures the result must be in two different bucket
// we keep min and max in each bucket, the result is the max value of successive bucket difference
// saying next_bucket.min-cur_bucket.max
if(nums == null || nums.length < 2) return 0;
int max = nums[0], min = nums[0];
for(int n: nums){
if(n > max) max = n;
if(n < min) min = n;
}
// if all same number
if(max == min) return 0;
int bsize = (int)Math.ceil((double)(max - min)/(nums.length - 1));
int[] bmin = new int[nums.length];
int[] bmax = new int[nums.length];
Arrays.fill(bmin, Integer.MAX_VALUE);
Arrays.fill(bmax, Integer.MIN_VALUE);
for(int n: nums){
int b = (n - min)/bsize;
bmin[b] = Math.min(n, bmin[b]);
bmax[b] = Math.max(n, bmax[b]);
}
int res = Integer.MIN_VALUE;
int pre = min;
for(int i = 0; i < nums.length; i++){
// empty bucket
if(bmin[i] == Integer.MAX_VALUE && bmax[i] == Integer.MIN_VALUE) continue;
res = Math.max(res, bmin[i] - pre);
pre = bmax[i];
}
res = Math.max(res, max - pre);
return res;
}
}
⚠️： min == max?
Radix sort 基数排序
- MSD: Most Significant Digit first
- LSD: Least Significant Digit first
一般而言用LSD比较多一些, stable.
Radix solution:
利用10base LSD的基数排序, 然后比较相邻两数之差。
O(n) time and O(n) space.
public class Solution {
public int maximumGap(int[] nums) {
// radix sort, after sort compare each nums[i] - nums[i-1]
// use 10 base, and longest length is 2^31 -> 10 digits
if(nums == null || nums.length < 2) return 0;
int max = nums[0];
for(int n: nums){
if(n > max) max = n;
} // for n
int[] copy = new int[nums.length];
int d = 1; // LSD
// using > instead of != will improve time for 2ms
while(max/d > 0){
int[] count = new int[10];
for(int n: nums){
count[(n/d)%10]++;
}
for(int i = 0; i < 9; i++){
count[i+1] += count[i];
}
for(int i = nums.length - 1; i >= 0; i--){
copy[--count[(nums[i]/d)%10]] = nums[i];
}
for(int i = 0; i < nums.length; i++){
nums[i] = copy[i];
}
d *= 10;
}
max = Integer.MIN_VALUE;
for(int i = 0; i < nums.length - 1; i++){
max = Math.max(max, nums[i+1] - nums[i]);
}
return max;
}
}