一:概述
这个算法的面试题目是:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。
二:具体说明
<1>第一种解法(初步解法)
这个解法的大致思路:使用任意一种时间复杂度为O(nlogn)的排序算法(如快速排序)给原数组排序,然后遍历排好序的数组,并对每两个相邻元素求差,最终得到最大差值。这个解法的时间复杂度是O(nlogn),在不改变原数组的情况下,空间复杂度是O(n)。
<2>第二种解法
利用计数排序的思想,先求出原数组的最大值max与最小值min的区间长度K(k=max-min+1),以及偏移量d=min.
- 创建一个长度为k的新数组Array。
- 遍历原数组,每遍历一个元素,就把新数组Array对应的下标值+1。例如原数组元素的值为n,则将Array[n-min]的值加1.遍历结束后,Array的一部分元素值变成了1或者更高的数值,一部分元素值仍然是0.
- 遍历新数组Array,统计出Array中最大连续出现0值得次数+!,即为相邻元素最大差值。
例如:给定一个无序数组{2, 6, 3, 4, 5, 10, 9},处理过程如图所示:
第一步,确定k(数组长度)和d(偏移量).
第二步,创建数组
第三步,遍历原数组,对号入座。
第四步,判断0值最多连续出现的次数,计算出最大相邻差。
<3>第三种解法
- 利用桶排序得思想,根据原数组得长度n,创建出n个桶,每一个桶代表一个区间范围。其中第1个桶从原数组得最小值min开始,区间跨度是(max - min)/(n -1)。
- 遍历原数组,把原数组每一个元素插入到对应的桶中,记录每一个桶的最大和最小值。
- 遍历所有的桶,统计出每一个桶的最大值,和这个桶右侧非空桶的最小值的差,数值最大的差即为原数组排序后的相邻最大差值。
例如:给出一个无序数组{2, 6, 3, 4, 5, 10, 9},处理过程如下所示:
第一步,根据原数组,创建桶,确定每个桶的区间范围。
第二步,遍历原数组,确定每个桶内的最大和最小值。
第三步,遍历所有的桶,找出最大相邻差。
最大相邻差= 9 -6 = 3
这个方法不需要像标准桶排序那样给每一个桶内部进行排序,只需要记录桶内的最大和最小值即可,所以时间复杂度稳定在O(n)
package com.algorithm6; /** *无序数组排序后的最大相邻差 */ public class UnsortArrayOfMaxDistance1 { public static int getMaxSortedDistance(int[] array) { // 得到数列的最大值和最小值 int max = array[0]; int min = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } if (min > array[i]) { min = array[i]; } } int d = max - min; // 如果max和min相等,说明数组所有元素都相等,返回0 if (d == 0) { return 0; } // 初始化桶 int bucketNum = array.length; Bucket[] buckets = new Bucket[bucketNum]; for (int i = 0; i < bucketNum; i++) { buckets[i] = null; // 初始化为null } // 确定数组元素所归属的桶下标 for (int i = 0; i < array.length; i++) { int index = ((array[i] - min) * (bucketNum - 1) / d); if (buckets[index] == null) { buckets[index] = new Bucket(); // 如果桶是null,先创建一个新的桶 } // 更新桶的最小值和最大值 if (buckets[index].min == null || buckets[index].min > array[i]) { buckets[index].min = array[i]; } if (buckets[index].max == null || buckets[index].max < array[i]) { buckets[index].max = array[i]; } } // 遍历桶,找到最大差值 int leftMax = buckets[0].max; int maxDistance = 0; for (int i = 1; i < buckets.length; i++) { if (buckets[i] == 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[]{2, 6, 3, 4, 5, 10, 9}; System.out.println(getMaxSortedDistance(array)); } }
标签:面试题,min,int,max,buckets,---,数组,array,排序 From: https://www.cnblogs.com/lyy123-Ly/p/18163583