首页 > 代码库 > 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.
Solution:
1 public class Solution { 2 public int maximumGap(int[] num) { 3 int len = num.length; 4 if (len<2) return 0; 5 if (len==2) return num[1]-num[0]; 6 7 int numMax = num[0], numMin = num[0]; 8 for (int i:num){ 9 numMax = Math.max(numMax,i);10 numMin = Math.min(numMin,i);11 }12 double temp = (double) numMax - numMin;13 int gap = (int) Math.ceil(temp/(len-1));14 15 int[] bucketMin = new int[len-1];16 int[] bucketMax = new int[len-1];17 Arrays.fill(bucketMin, Integer.MAX_VALUE);18 Arrays.fill(bucketMax, Integer.MIN_VALUE);19 for (int i:num){20 int index = (i-numMin)/gap;21 if (i==numMax) index = len-2;22 if (i>bucketMax[index]) bucketMax[index] = i;23 if (i<bucketMin[index]) bucketMin[index] = i;24 }25 26 int res = Integer.MIN_VALUE;27 int pre = bucketMax[0];28 for (int i=1;i<len-1;i++)29 if (bucketMin[i] == Integer.MAX_VALUE) continue;30 else {31 if (res<(bucketMin[i]-pre))32 res = bucketMin[i]-pre;33 pre = bucketMax[i];34 }35 36 return res;37 }38 }
LeetCode-Maximum Gap
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。