最小间距

算法

Posted by CH on May 24, 2020

题目

给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。

如果数组元素个数小于 2,则返回 0。

要求:时间复杂度O(n).

示例

输入: [3,6,9,1]

输出: 3

解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

题干

排序之后

相邻元素之间最大的差值

时间和空间复杂度O(n)

思路

数组空间解法

找出数组中的最大值和最小值 最大值-最小珠+1 = 新数组的长度

然后循环旧数组 将旧数组的值-最小值 作为下标 旧数组的值作为值 赋值给新数组

循环一遍这样我们的新数组就具备以下特性

1。数组中元素是有序的

2。数组中在旧数组不存在的值为0

这样我们就可以遍历新数组 如果下一个值为0 即为间隙 divider++ 如果不为0 divider=1重置

选取maxdivider即可

排序解法

题目中要求时间和空间复杂度为线性 那么从排序的角度出发 哪些排序算法是线性的

能不能以此作为突破口

基数排序

时间复杂度为 O (nlog(r)m) 其中r为所采取的基数,而m为堆数

在良好的条件下是可以达到O(n)的复杂度

基数排序有两种LSD(Least Significant Digit first)) MSD(Most Significant Digit first)

一种为低位排序 一种为高位排序

例子 比如lsd 将个位按0~9分组 接着十位 0~9分组 直到最高位链接后有序

字典树算法

解答

数组空间解法

class Solution {
    public int maximumGap(int[] nums) {
  if(nums.length<2){
            return 0;
        }
        int max =  findMax(nums);
        int min = findMin(nums);

        int size = max-min+1;//数组池的长度
        System.out.println("大小:"+size);
        int[] container = new int[size];
        for(int i=0;i<nums.length;i++){
            container[nums[i]-min]=nums[i];
        }
    
        System.out.println("");
        int maxDivider = 0;
        int divider = 1;
        for(int i=0;i<container.length;i++){
            if(container[i]==0){
                divider++;
                if(divider>maxDivider){
                    maxDivider = divider;
                }
            }else {
                divider=1;
            }
        }
        return maxDivider;
    }

     public static int findMax(int[] arr){
        int max = arr[0];
        for(int num:arr){
            if(num>max){
                max = num;
            }
        }
        return max;
    }

    public static int findMin(int[] arr){
        int min = arr[0];
        for(int num:arr){
            if(num<min){
                min = num;
            }
        }
        return min;
    }
}

时空复杂度分析

如果采用数组空间解法 时间复杂度为O(n) 空间复杂度我理解是为O(n)但是运行在leetcode超出内存限制 故而需要找到更好的方法

结语

此题难度较高 体现在时间复杂度上 线性要求