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.
New LeetCode problem. The algorithm is referred from the application of Pigeonhole principle. It is beautiful, smart and very easy to understand.Ah, that's why I love math (even though I am not good at it): it always solves the hard problem by the simplest principles.
Update: 2015 - 03 - 04
Briefly, the maximum gap between two successive integers must lie between the maximum number in one bucket and the minimum number in the next bucket.
public class MaxGap { public int maximumGap(int[] nums) { if (nums == null || nums.length < 2) return 0; if (nums.length == 2) { return Math.abs(nums[0] - nums[1]); } int max = nums[0]; int min = nums[0]; int len = nums.length; for (int i = 0; i < len; i++) { max = Math.max(nums[i], max); min = Math.min(nums[i], min); } int[] max_buckets = new int[len - 1]; int[] min_buckets = new int[len - 1]; for (int i = 0; i < len - 1; i++) { max_buckets[i] = -1; min_buckets[i] = Integer.MAX_VALUE; } double interval = ((double)max - (double)min) / (double)(len - 1); for (int i = 0; i < len; i++) { if (nums[i] == max) { max_buckets[len - 2] = nums[i]; continue; } int b = (int)((nums[i] - min) / interval); max_buckets[b] = Math.max(max_buckets[b], nums[i]); min_buckets[b] = Math.min(min_buckets[b], nums[i]); } if (min_buckets[len - 2] == Integer.MAX_VALUE) { min_buckets[len - 2] = max; } int max_gap = 0; int index1 = len - 2, index2 = len - 3; while (index2 >= 0 && index1 > index2) { while (index2 >= 0 && max_buckets[index2] == -1) { index2--; } while (index1 > index2 && min_buckets[index1] == Integer.MAX_VALUE) { index1--; } max_gap = Math.max(max_gap, min_buckets[index1] - max_buckets[index2]); index2--; index1--; } return max_gap; } }
No comments:
Post a Comment