php源码网站建设教程,西安网站seo,深圳市水平线室内设计有限公司,小程序开放平台问题#xff1a;
数组排序之后的相邻数的最大差值#xff1b;
嗯#xff0c;你可以排序#xff0c;然后找相邻的最大差值。
但是你觉得这么简单我写他干啥。
最优解#xff1a;时间复杂度O(N)#xff0c;空间O(1) 那我们开始说这种方法#xff1a;
1#xff09;遍…问题
数组排序之后的相邻数的最大差值
嗯你可以排序然后找相邻的最大差值。
但是你觉得这么简单我写他干啥。
最优解时间复杂度O(N)空间O(1) 那我们开始说这种方法
1遍历所有数找到最小值和最大值min和max
2设数组长度为n我们准备n1个桶
3把max放进最后一个桶里min放到第一个桶里
4每一个桶都负责放一个范围内的数字负责的范围大小是(max-min)/n。
比如长度为10最小值为10最大值为110那么准备11个桶第一个桶放[10,20)的数字第二个桶放[20,30)的数字......
重点来啦因为有n1个桶有n个数字我们就发现了一个问题必定会有空的桶
为什么我们一定要有空的桶呢 这样我们就可以做到桶内的相邻数字的差一定没有不同桶之间的数字的差大
有了这个结论我们可以做什么呢
其实找相邻桶和桶之间的差就好啦桶内的那些情况根本不用关心 想到这里我们发现桶里根本不用关心到底有几个数他们的差是多少只要记录每个桶的最大值最小值即可。 最后一点小问题啦对于一个数num他应该放在哪个桶最好推个公式吧 它应该被放在(num-min)*len/(max-min)这个桶里。也不难推。
最后就是写代码啦。
public class MaxGap {public static int maxGap(int[] nums) {if (nums null || nums.length 2) {return 0;}int len nums.length;int min Integer.MAX_VALUE;int max Integer.MIN_VALUE;for (int i 0; i len; i) {min Math.min(min, nums[i]);max Math.max(max, nums[i]);}if (min max) {return 0;}boolean[] hasNum new boolean[len 1];//记录是否空int[] maxs new int[len 1];//桶内最大值int[] mins new int[len 1];//桶内最小值int bid 0;//放入桶中for (int i 0; i len; i) {bid bucket(nums[i], len, min, max);mins[bid] hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];maxs[bid] hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];hasNum[bid] true;}int res 0;int lastMax maxs[0];int i 1;//相邻桶求最大差值for (; i len; i) {if (hasNum[i]) {res Math.max(res, mins[i] - lastMax);lastMax maxs[i];}}return res;}public static int bucket(long num, long len, long min, long max) {return (int) ((num - min) * len / (max - min));}public static void main(String[] args) {int[] arr {};System.out.println(maxGap(arr));}}
