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

最大间距(桶排序)

程序员文章站 2022-05-12 15:57:55
...

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

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

示例 1:

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

输入: [10] 输出: 0 解释: 数组元素个数小于 2,因此返回 0。 说明:

你可以假设数组中所有元素都是非负整数,且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-gap
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

首先简单来讲讲桶排序这个算法,这里的桶代表的是一个区间范围,每个桶的区间长度一般都是一样的,比如说给定数组 [1,5,7,10],这里如果我们分 10 个桶,那么每个桶的区间长度就是 1,等同于每个桶其实就对应一个数,如果这里我们分 1 个桶,那么这个桶的区间范围就是 1 ~ 10,当然这里我给的两个例子都是极端的例子,在实际应用上我们应该结合实际情况合理分配桶。

但是基本来说桶的范围和个数是由数组中最大值、最小值以及数组中的元素的个数来决定的,这样可以保证使用最少的桶覆盖所有的可能性。

这个题目要求我们求数组排序好后,相邻数的最大差值,这里我们首先遍历一遍数组得到最大值、最小值,仔细想想的话,如果排序好的数组当中的元素都是等间隔的,类似 [2,4,6,8,10] ,在数组长度,最大最下值确定的情况下,在这种等间隔的情况下,求得的相邻数的最大差值是最小的,这很好理解,因为同等资源都被等量分配了,不存在分配多和少的结果。

因此,如果我们按这个等量分配的长度来定义桶的长度的话,我们其实并不需要考虑桶内元素的差值,我们需要做的只是记录每个桶中所有元素的最大值和最小值,然后拿这两个值去和相邻的桶的最大值和最小值做差。这样下来可以保证时间复杂度是 O(n) 的。

int maximumGap(int* nums, int numsSize){
    if(numsSize<2)
        return 0;
    int min=INT_MAX;
    int max=INT_MIN;
    for(int i=0;i<numsSize;i++)
    {
        min=min<nums[i]?min:nums[i];
        max=max>nums[i]?max:nums[i];
    }
    //在 n 个数下,形成的两两相邻区间是 n - 1 个
    int len=max-min+1; //区间总长度
    int gap_size=len/numsSize+1;//桶长度 = 区间总长度 / 区间总个数
    int basket=len/gap_size+1;//桶个数 = 区间总长度 / 桶长度
    // 这里考虑到实现的方便,多加了1个桶
    // 例子,[2,4,6,8], 桶的长度 = (8 - 2) / (4 - 1) = 2
    // 桶的个数 = (8 - 2) / 2 = 3
    // 已知一个元素,需要定位到桶的时候,一般是 (当前元素 - 最小值) / 桶长度
    // 这里其实利用了整数除不尽向下取整的性质
    // 但是上面的例子,如果当前元素是 8 的话 (8 - 2) / 2 = 3,对应到 3 号桶
    //如果当前元素是 2 的话 (2 - 2) / 2 = 0,对应到 0 号桶
    // 你会发现我们有 0,1,2,3 号桶,实际用到的桶是 4 个,而不是 3 个
    // 透过例子应该很好理解,但是如果要说根本原因,其实是开闭区间的问题
    // 这里其实 0,1,2 号桶对应的区间是 [2,4),[4,6),[6,8)
    // 那 8 怎么办?多加一个桶,3 号桶对应区间 [8,10)
    bool *state=(bool *)malloc(sizeof(bool)*basket);
    memset(state,0,sizeof(bool)*basket);
    int *min_save=(int *)malloc(sizeof(int)*basket);
    int *max_save=(int *)malloc(sizeof(int)*basket);
    for(int i=0;i<numsSize;i++)
    {
        int offset=nums[i]-min;
        int pos=offset/gap_size;
        if(!state[pos])
        {
            state[pos]=true;
            min_save[pos]=nums[i];
            max_save[pos]=nums[i];
        }
        else
        {
            min_save[pos]=min_save[pos]<nums[i]?min_save[pos]:nums[i];
            max_save[pos]=max_save[pos]>nums[i]?max_save[pos]:nums[i];
        }
    }
    int start=0;
    int max_len=0;
    while(start<basket)
    {
        if(!state[start])start++;
        else
        {
            int first=max_save[start];
            start++;
            while(start<basket&&!state[start])start++;
            if(start<basket)
            {
                max_len=max_len>min_save[start]-first?max_len:min_save[start]-first;
            }
            else break;
        }
    }
    free(state);
    free(min_save);
    free(max_save);
    return max_len;
}