一道神奇的口试题---无序数组排序后的最大相邻差

一：概述
　　这个算法的口试题目是：有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽大概低。　　
　　

 
 
二：具体说明

　　第一种解法(初步解法)
　　　　这个解法的大致思路：使用任意一种时间复杂度为O(nlogn)的排序算法(如快速排序)给原数组排序，然后遍历排好序的数组，并对每两个相邻元素求差，最终得到最大差值。这个解法的时间复杂度是O(nlogn)，在不改变原数组的环境下，空间复杂度是O(n)。
　　　第二种解法
　　　　利用计数排序的头脑，先求出原数组的最大值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值最多连续出现的次数，计算出最大相邻差。

 　　　　　　第三种解法

• 　　　　　　利用桶排序得头脑，根据原数组得长度n，创建出n个桶，每一个桶代表一个区间范围。其中第1个桶从原数组得最小值min开始，区间跨度是(max - min)/（n -1）。
  
• 　　　　　　遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大和最小值。
  
• 　　　　　　遍历全部的桶，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。
  

　　　　例如：给出一个无序数组{2, 6, 3, 4, 5, 10, 9}，处理过程如下所示：
　　　　第一步，根据原数组，创建桶，确定每个桶的区间范围。

 　　　　第二步，遍历原数组，确定每个桶内的最大和最小值。

 　　　　第三步，遍历全部的桶，找出最大相邻差。

 最大相邻差= 9 -6 = 3
这个方法不必要像标准桶排序那样给每一个桶内部举行排序，只必要记录桶内的最大和最小值即可，以是时间复杂度稳定在O(n)

1. package com.algorithm6;
2. /**
3. *无序数组排序后的最大相邻差
4. */
5. public class UnsortArrayOfMaxDistance1 {
6.     public static int getMaxSortedDistance(int[] array) {
7.         // 得到数列的最大值和最小值
8.         int max = array[0];
9.         int min = array[0];
10.         for (int i = 1; i < array.length; i++) {
11.             if (max < array[i]) {
12.                 max = array[i];
13.             }
14.             if (min > array[i]) {
15.                 min = array[i];
16.             }
17.         }
18.         int d = max - min;
19.         // 如果max和min相等，说明数组所有元素都相等，返回0
20.         if (d == 0) {
21.             return 0;
22.         }
24.         // 初始化桶
25.         int bucketNum = array.length;
26.         Bucket[] buckets = new Bucket[bucketNum];
27.         for (int i = 0; i < bucketNum; i++) {
28.             buckets[i] = null; // 初始化为null
29.         }
31.         // 确定数组元素所归属的桶下标
32.         for (int i = 0; i < array.length; i++) {
33.             int index = ((array[i] - min) * (bucketNum - 1) / d);
34.             if (buckets[index] == null) {
35.                 buckets[index] = new Bucket(); // 如果桶是null，先创建一个新的桶
36.             }
37.             // 更新桶的最小值和最大值
38.             if (buckets[index].min == null || buckets[index].min > array[i]) {
39.                 buckets[index].min = array[i];
40.             }
41.             if (buckets[index].max == null || buckets[index].max < array[i]) {
42.                 buckets[index].max = array[i];
43.             }
44.         }
46.         // 遍历桶，找到最大差值
47.         int leftMax = buckets[0].max;
48.         int maxDistance = 0;
49.         for (int i = 1; i < buckets.length; i++) {
50.             if (buckets[i] == null) {
51.                 continue;
52.             }
53.             if (buckets[i].min - leftMax > maxDistance) {
54.                 maxDistance = buckets[i].min - leftMax;
55.             }
56.             leftMax = buckets[i].max;
57.         }
58.         return maxDistance;
59.     }
61.     private static class Bucket {
62.         Integer min;
63.         Integer max;
64.     }
66.     public static void main(String[] args) {
67.         int[] array = new int[]{2, 6, 3, 4, 5, 10, 9};
68.         System.out.println(getMaxSortedDistance(array));
69.     }
73. }

复制代码

 
 
 
 
 
 
 
 
 
 
 
　　
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。