欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode算法题解:一个无序数组排序后的任意两个相邻元素的最大差值

程序员文章站 2024-03-15 22:48:36
...

两个相邻元素的最大差值

题目:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?

解法一:直接快排然后求差值

时间复杂度O(nlogn),空间复杂度O(n)

使用任意一种时间复杂度为O(nlogn)的排序算法(如快排)给原数组排序,然后遍历排好序的数组,并对每两个相邻元素求差,最终得到最大差值。

解法二:计数排序的思想利用数组下标求解

步骤:

  1. 利用计数排序的思想,先求出原数组的最大值max和最小值min的区间长度k(k = max - min + 1) ,以及偏移量d = min
  2. 创建一个长度为k的新数组Array
  3. 遍历原数组,每遍历一个元素,就把新数组Array对应下标的值 + 1 。例如原数组元素的值为n,则将Array[n - min]的值加1.遍历结束后,Array的一部分元素值变成了1或更高的数值,一部分元素值仍然是0。
  4. 遍历新数组Array,统计出Array中最大连续出现0值得次数 + 1,即为相邻元素最大差值

解法三:桶排序的思想

  1. 利用桶排序的思想,根据原数组的长度7,创建出个桶,每一个桶代表 个区间范围。其中第1个桶从原数组的最小值mn开始,区间跨度是(max-mn)/(n-1)。

  2. 遍历原数组,把原数组每一个元素插入到对应的桶中,记录每一个桶的最大和最小值。

  3. 遍历所有的桶,统计出每一个桶的最大值, 和这个桶右侧非空桶的最小值的差,数值最大的差即为原数组排序后的相邻最大差值。

package some_problem;/**
 * Copyright (C), 2019-2020
 * author  candy_chen
 * date   2020/7/20 21:22
 * version 1.0
 * Description: 求出一个无序数组排序后的任意两个相邻元素的最大差值
 */

/**
 *
 */
public class GetMaxSortedDistance {
    /**
     * 桶
     */
    private static class Bucket{
        Integer min;
        Integer max;
    }
    public static int getMaxSortedDistance(int[] array){
        //1.得到数列的最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i=0;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;
        }

        //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].min==null || buckets[index].min>array[i]){
                buckets[index].min = array[i];
            }
            if (buckets[index].max == null || buckets[index].max<array[1]){
                buckets[index].max = array[i];
            }
        }
        //4.遍历桶,找到最大差值
        int leftMax = buckets[0].max;
        int maxDistance = 0;
        for (int i=1;i<buckets.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;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2,6,3,4,5,10,9};
        System.out.println(getMaxSortedDistance(array));
    }
}

参考链接:漫画算法:无序数组排序后的最大相邻差值