毕业设计做课程网站好,南充网站建设有哪些,福建建设厅安全员报名网站,wordpress 安装插件无序数组排序后的最大相邻差
问题#xff1a;一个无序的整型数组#xff0c;求出该数组排序后的任意两个相邻元素的最大差值#xff1f;要求时间和空间复杂度尽可能低。
三种方法#xff1a; 排序后计算比较 简介#xff1a;用任意一种时间复杂度为 O ( n log n ) O…无序数组排序后的最大相邻差
问题一个无序的整型数组求出该数组排序后的任意两个相邻元素的最大差值要求时间和空间复杂度尽可能低。
三种方法 排序后计算比较 简介用任意一种时间复杂度为 O ( n log n ) O(n \log n) O(nlogn) 的排序算法给原数组排好序。然后遍历排序好的数组并对每两个相邻元素求差最终得到最大差值。思考时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)在不改变原数组的情况下空间复杂度为 O ( n ) O(n) O(n)存储排序好的数组。但这道题显然不是用来排序的。 利用计数排序的思想 简介求出原数组的最大最小值max和min区间长度kmax - min 1偏移量 min。创建一个长度为k的数组。遍历原数组若原数组值为n则array[n-min]的值加1。遍历新数组统计最大连续出现0值的次数1就是相邻元素的最大差值。思考若原数组是 1 1000000310000006 这三个元素呢没办法了想到了桶排序好像可以解决这个问题 利用桶排序的思想 简介根据原数组长度n创建n个桶每个桶代表一个区间范围区间跨度是(max - min) / (n-1)。遍历原数组对应元素放到桶中记录每个桶的最大最小值。遍历桶统计每个桶的最大值和右侧非空桶的最小值的差数值最大的差即为最大相邻差。 代码 public class MaxSortedDistance {public static int getMaxSortedDistance(int[] array){//1.得到原数组的最大值和最小值 和 区间跨度int max array[0];int min array[0];for(int i1; iarray.length; i) {if(array[i] max) {max array[i];}if(array[i] min) {min array[i];}}int d max - min;//如果max和min相等说明数组所有元素都相等返回0if(d 0){return 0;}//2.初始化桶桶的数量和元素的数量一样多int bucketNum array.length;Bucket[] buckets new Bucket[bucketNum];for(int i 0; i bucketNum; i){buckets[i] new Bucket();}//3.遍历原始数组确定每个桶的最大最小值for(int i 0; i array.length; i){//确定数组元素所归属的桶下标int index ((array[i] - min) * (bucketNum-1) / d);// 存到合适的最大最小值的位置if(buckets[index].minnull || buckets[index].minarray[i]){buckets[index].min array[i];}if(buckets[index].maxnull || buckets[index].maxarray[i]){buckets[index].max array[i];}}//4.遍历桶找到最大差值int leftMax buckets[0].max; // 存储第一个桶的最大值int maxDistance 0;for (int i1; ibuckets.length; i) {// 如果右侧的桶没有最小值就直接遍历下一个桶if (buckets[i].min null) { continue;}// 记录好最大差if (buckets[i].min - leftMax maxDistance) {maxDistance buckets[i].min - leftMax;}leftMax buckets[i].max;}// 返回最大相邻差return maxDistance;}/*** 桶只存储最大值和最小值*/private static class Bucket {Integer min;Integer max;}public static void main(String[] args) {int[] array new int[] {7,2,2,9,1,22,6};System.out.println(getMaxSortedDistance(array));}
} 时间复杂度和空间复杂度都是 O ( n ) O(n) O(n)
