首页 > 代码库 > Leetcode: Maximum Gap
Leetcode: 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.
官方版（桶排序）：
假设有N个元素A到B。
那么最大差值不会小于ceiling[(B - A) / (N - 1)]
令bucket（桶）的大小len = ceiling[(B - A) / (N - 1)]
对于数组中的任意整数K，很容易通过算式loc = (K - A) / len找出其桶的位置，然后维护每一个桶的最大值和最小值
由于同一个桶内的元素之间的差值至多为len - 1，因此最终答案不会从同一个桶中选择。
对于每一个非空的桶p，找出下一个非空的桶q，则q.min - p.max可能就是备选答案。返回所有这些可能值中的最大值。
这里A是min，B是max，桶有num.length - 1个。min, max不参与放入桶中，除了min和max之外还有N-2个数字和N-1个桶，所以一定有一个空桶。因为有空桶的存在所以要用一个previous变量来代表上一个非空的桶的max。previous初始化为min，这样min就考虑了虽然min不在桶中。还要记得考虑max，所以最后遍历了桶之后还要再比一次max
本算法O(n)时间和空间
还要注意math.floor,不能用，要用math.ceil比如：2/2.667 = 0.7499062617172854, 期望是：1，但是floor会给0，ceil才能给1.
1 public class Solution { 2 public int maximumGap(int[] num) { 3 if (num == null || num.length < 2) 4 return 0; 5 // get the max and min value of the array 6 int min = num[0]; 7 int max = num[0]; 8 for (int i:num) { 9 min = Math.min(min, i);10 max = Math.max(max, i);11 }12 // the minimum possibale gap, ceiling of the integer division13 int gap = (int)Math.ceil((double)(max - min)/(num.length - 1));14 int[] bucketsMIN = new int[num.length - 1]; // store the min value in that bucket15 int[] bucketsMAX = new int[num.length - 1]; // store the max value in that bucket16 Arrays.fill(bucketsMIN, Integer.MAX_VALUE);17 Arrays.fill(bucketsMAX, Integer.MIN_VALUE);18 // put numbers into buckets19 for (int i:num) {20 if (i == min || i == max)21 continue;22 int idx = (i - min) / gap; // index of the right position in the buckets23 bucketsMIN[idx] = Math.min(i, bucketsMIN[idx]);24 bucketsMAX[idx] = Math.max(i, bucketsMAX[idx]);25 }26 // scan the buckets for the max gap27 int maxGap = Integer.MIN_VALUE;28 int previous = min;29 for (int i = 0; i < num.length - 1; i++) {30 if (bucketsMIN[i] == Integer.MAX_VALUE && bucketsMAX[i] == Integer.MIN_VALUE)31 // empty bucket32 continue;33 // min value minus the previous value is the current gap34 maxGap = Math.max(maxGap, bucketsMIN[i] - previous);35 // update previous bucket value36 previous = bucketsMAX[i];37 }38 maxGap = Math.max(maxGap, max - previous); // updata the final max value gap39 return maxGap;40 }41 }
Leetcode: Maximum Gap
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。