网站建设需要包含什么,网站如何验收,常州溧阳市建设局网站,公司网站seo公司目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介绍 …
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 给定一个无序数组arr求数组arr排好序之后相邻数间的最大差值 如 arr [1,9,10] 结果为 9 - 1 8
解决方案
原问题 1、首先创建一个桶数组每一个桶只记录当前桶中的最大值和最小值桶数组的长度为arr.len-1 2、获取整个数组中的最大值和最小值将最大值放入bucket[arr.len] 3、计算桶的范围(最大值-最小值)/桶数量-1 4、根据桶范围和每一个值计算出来每一个值的桶编号放入桶中 5、遍历桶计算最长的空桶子数组将该子数组的前后桶拿出来后桶的最小值-前桶的最大值即可。
代码编写
java语言版本
原问题 方法一: /*** 二轮测试获取数组排序后相邻之间的最大值* param arr* return*/public static int getMaxSubCp1(int[] arr) {if (arr null || arr.length 0) {return -1;}if (arr.length 1) {return 0;}// 桶个数int bNum arr.length1;// 桶列表,这里长度不会改变的使用数组类型Record[] records new Record[bNum 1];init(records);Record maxAndMin getMaxAndMin(arr);int max maxAndMin.getMaxValue();int min maxAndMin.getMinValue();// 桶中的范围int dis (int)Math.ceil((max - min 1) / (bNum-1));// 最大值放入最后一个桶records[bNum].updateMaxOrMin(max);// 剩下的开始分类放入桶中for (int i 0; i arr.length; i) {if (max arr[i]) {continue;}// 桶号int bucketNum (arr[i] - min) / dis;records[bucketNum].updateMaxOrMin(arr[i]);}// 找到桶中第一个不为空的indexint noEmpty 0;while (records[noEmpty].isEmpty()) {noEmpty;}// 记录上一个非空位置int lastNoEmpty noEmpty;int res 0;// 循环找到除当前位置外的非空桶while (noEmpty records.length) {if (noEmpty ! lastNoEmpty !records[noEmpty].isEmpty()){// 找到一个res Math.max(res, records[noEmpty].getMinValue() - records[lastNoEmpty].getMaxValue());lastNoEmpty noEmpty;}noEmpty;}return res;}/*** 初始化* param records*/private static void init(Record[] records) {for (int i 0; i records.length; i) {records[i] new Record(Integer.MIN_VALUE, Integer.MAX_VALUE);}}/*** 获取arr中的最值* param arr* return*/private static Record getMaxAndMin(int[] arr) {int min arr[0];int max arr[0];for (int i 0; i arr.length; i) {min Math.min(arr[i], min);max Math.max(arr[i], max);}return new Record(max, min);}/*** 每一个桶只记录最大值和最小值就行*/protected static class Record {private Integer maxValue;private Integer minValue;private LinkedListInteger bucket;public Record(Integer maxValue, Integer minValue) {this.maxValue maxValue;this.minValue minValue;}/*** 拓展构造函数* param maxValue* param minValue* param bucket*/public Record(Integer maxValue, Integer minValue, LinkedListInteger bucket) {this.maxValue maxValue;this.minValue minValue;this.bucket bucket;}public Integer getMaxValue() {return maxValue;}public void setMaxValue(Integer maxValue) {this.maxValue maxValue;}public Integer getMinValue() {return minValue;}public void setMinValue(Integer minValue) {this.minValue minValue;}/*** 判断当前值是否能够更新最值* param value*/public void updateMaxOrMin(int value) {this.maxValue Math.max(this.maxValue, value);this.minValue Math.min(this.minValue, value);}/*** 当前桶是否为空* 最值没有更新过*/public boolean isEmpty() {return this.maxValue Integer.MIN_VALUE this.minValue Integer.MAX_VALUE;}}public static void main(String[] args) {System.out.println(getMaxSubCp1(new int[]{1,3,9,10}));}c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
这里有几个点需要注意一下 1、桶的长度为arr.len1但是除了最大值外其他的数都不能到最大的桶中这个就是通过计算范围时除数是桶数-1来控制的并且向上取整来保证。 2、桶的个数比arr的长度多一个1就表示一定会出现一个或者多个空桶那么我就想假如是1~10桶个数是11个间隔是1这样的话出现空桶也只能计算出来最大长度是1如果存在间隔为2的一定会出现两个空桶。 3、第三个问题就是计算空桶最大长度的问题刚开始我觉得要求连续的空桶长度那么要两个游标在计算完成后一个游标要循环到下一个空桶段的起点然后再开始继续判断其实换一种思路来看连续的桶也可以看成是空桶段只不过空桶段中没有空桶而已所以问题就变成了如果当前index不是起点并且不是空桶那么就计算长度并将当前位置作为下一个的起点整个思路的代码量就减少了很多。这个解释有点不太好理解大家可以借鉴一下最后那个计算最长空桶段的代码。
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
