数组排序之后相邻数的最大差值

电玩女神 2022-05-29 11:51 192阅读 0赞

![Center][]

import java.util.*;
    //数组排序之后相邻数的最大差值
    public class MaxMinusArr{
    	//方法一、获得相邻数的最大差值
        public static int getMaxMinusArr(int[]arr)
        {
               int max=Integer.MIN_VALUE;
               if(arr==null||arr.length<2)
               {
                	 return -1;
               }
               for(int i=0;i<arr.length-1;i++)
               {  
               	   int k=arr[i+1]-arr[i];
               	   max=Math.max(max,k);
               }
              return max;
              
        }
        //方法二(基于桶排序的思想)
        public static int getMaxMinusArr02(int[]arr)
        {
              if(arr==null||arr.length<2)
              {
              	 return -1;
              }
              int len=arr.length; //数组的长度
              int min=Integer.MAX_VALUE;
              int max=Integer.MIN_VALUE;
              for(int i=0;i<len;i++)
              {
              	  min=Math.min(min,arr[i]); //获得数组中的最小值
              	  max=Math.max(max,arr[i]); //获得数组中的最大值
              }
              if(min==max)
              {
              	 return 0;
              }
              boolean[]hasNum=new boolean[len+1];
              int[]maxs=new int[len+1];
              int[]mins=new int[len+1];
              int bid=0;
               for(int i=0;i<len;i++)
               {
               	  bid=bucket(arr[i],len,min,max); //算出桶号
               	  mins[bid] = hasNum[bid] ? Math.min(mins[bid], arr[i]) : arr[i];
               	  maxs[bid] = hasNum[bid] ? Math.min(maxs[bid], arr[i]) : arr[i];
                  hasNum[bid]=true;
               }
               int res=0;
               int lasMax=maxs[0];
               int  i=1;
               for(;i<=len;i++)
               {
               	   if(hasNum[i])
               	   {
               	   	 res=Math.max(res,mins[i]-lasMax);
               	     lasMax=maxs[i];
               	   }
               }
              return res;
        }
        //使用long类型防止相乘时溢出,获得当前数需要放置的桶位置
        public static int bucket(long num,long len,long min,long max)
        {
                return (int)((num-min)*len/(max-min));
        }
        public static int[]generateArr(int size)
        {
        	 int[]arr=new int[size];
        	 for(int i=0;i<size;i++)
        	 {
        	 	  arr[i]=(int)(Math.random()*100);
        	 }
        	 Arrays.sort(arr);
        	 return arr;
        }
        //打印生成的矩阵
        public static void printArr(int[]arr)
        {
        	for(int i=0;i<arr.length;i++)
        	{
        		System.out.print(arr[i]+" ");
        	}
            System.out.println();
        }
    	public static void main(String[]args)
    	{      int size=20;
               int[]arr=generateArr(size);
               printArr(arr);
               System.out.println(getMaxMinusArr(arr));
               System.out.println(getMaxMinusArr02(arr));
    	}
    }

![Center 1][]

[Center]: /images/20220529/1a38bc4ed03b45ee91cbda98c0300c75.png
[Center 1]: /images/20220529/acb4836aa21544e59d65cabb6e2bb2d3.png