最大间距(桶排序)
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。
如果数组元素个数小于 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;
}