无序数组的相邻最大差值

深藏阁楼爱情的钟 2022-06-08 06:39 179阅读 0赞

### 题目描述： ###

请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。  
给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。  
测试样例：  
\[9,3,1,10\],4  
返回：6

### 问题分析： ###

有无序的实数列V\[N\]，要求求里面大小相邻的实数的差的最大值，关键是 要求线性空间和线性时间用基于桶排序的方式。  
注意到，最后只需要求间隔的最大值，所以任何间隔小于bar= (max - min)/(N-1) 的值都可以不计。  
这样，首先求随机数组中的max , min 这些都是线性时间的

然后，分配从\[min, max\]间分配(N-1)个桶，每个桶是一个有序实数对，(a,b)  
将所有数往桶里塞，把欲塞进去的数记为x，(空桶)如果桶里本身没有数，那么a=b=x  
(桶内已有数)如果x>b，那么b=x,如果x

### 代码实现 ###

import java.util.*;
    
    public class MaxDivision { 
      //无序数组A有，有n个元素。求排序后相邻最大差值，要求复杂度为O(n)
     public int findMaxDivision(int[] A, int n) {
            // write code here
            int max, min, i;
            //先求出无序数组的最大最小值max，min
            max = min = A[0];
            for(i = 1; i < n; i++){
                if(A[i] > max) max = A[i];
                if(A[i] < min) min = A[i];
            }
            int bar, pos;
            double tempBar;
            //求出排序后数组相邻差值的平均值
            tempBar = (max-min)*1.0/(n-1);
            bar = (int) Math.ceil(tempBar);
            //新建数组，[0]放桶中最小，[1]放桶中最大
            int[][] bucket = new int[n][2];
            //数组全部初始化为0
            for(i = 0; i < n; i++){
                bucket[i][0] = bucket[i][1] = 0;
            }
            for(i = 0; i < n; i++){
                //原无序数组中，每个元素与最小值的差值，是相邻差值平均值的多少倍
                pos = (A[i]-min)/bar;
                if(bucket[pos][0] == 0){
                    //初始时桶中最大最小值赋值相等
                    bucket[pos][0] = bucket[pos][1] = A[i];
                }else{
                    // 桶中最小值的更新
                    if(A[i] < bucket[pos][0]) bucket[pos][0] = A[i];
                    // 桶中最大值的更新
                    if(A[i] > bucket[pos][1]) bucket[pos][1] = A[i];
                }
            }
            //定义diff为相邻差值，max_diff为相邻最大差值
            int diff, max_diff = 0;
            int temp = 0;
            for(i = 1; i < n; i++){
                if(bucket[i][0] == 0){
                    temp++;
                }else{
                    //相邻两个桶，下一个桶最小值减去上一个桶最大值，就是相邻差值
                    diff = bucket[i][0] - bucket[i-1-temp][1];
                    if(max_diff < diff) max_diff = diff;
                    temp = 0;
                }
            }
            return max_diff;
        }
       // 具体实例
      public static void main(String[] args) {
            MaxDivision md = new MaxDivision();
            int[] b = {
       2,4,2,8,5,7};
            int Maxdiff = md.findMaxDivision(b,6);
            System.out.println(Maxdiff);
        }
    }