题目描述
164. Maximum Gap
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Example 1:
Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
(3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.
Note:
- You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
- Try to solve it in linear time/space.
题意:给一个无序数组,返回将这个数组排好序后相邻两个元素差的最大值。
算法1
(桶排序)
题解:这一题首先肯定是需要排序的,但是题目想求的时间复杂度,我们只能考虑非基于比较排序的方法了。这题其实我刚开始也不会写,看了题解之后使用了桶排序+鸽笼原理来解决上述问题。我这里着重分析一下其原理。
首先我们遍历一遍数组,找到数组中的最大值和最小值Max
和Min
,那么整个数组中首尾两个数的间隔就是Max - Min
,总共有n
个数,它们之间有n - 1
个间隔,为了使间隔最大值最小,那么根据贪心的思路,必然是每个间隔仅可能相等比较好。我们记gap =ceil((Max - Min)/(n - 1))
,ceil函数是向上取整的函数。我们可以得到:
$Max - Min \leq gap \*(n - 1)\to Max\leq Min + gap\*(n - 1)$
我们将每个桶的大小就设置成这个值,那我们总共需要n
个桶,当且仅当上面不等式成立时,第n
个桶中有一个最大值。对于每个桶,我们记录这个桶内的最大值和最小值,以及是否被用过。并且每个桶控制的区间分别为。
另一个比较直观的分析是,因为每一个桶内的元素差值都小于gap
,而根据贪心思想,相邻两个元素差值的最大值肯定大于等于gap
,我们没有必要比较同一个gap
内的元素。
[Min,Min + gap)
[Min + gap,Min + 2 * gap)
...
[Min + (n - 2) * gap,Min + (n - 1) * gap)
[Min + (n - 1) * gap,Min + n * gap) 这个区间内只可能有Max。
现在我们考虑除去Max
和Min
这两个元素和最后一个区间,剩下n - 2
个元素需要放在前面n - 1
个桶中,那么至少有一个桶中没有放置元素,即空桶:
假设第一个区间内没有放置额外的元素,那么这个区间内只有一个Min
,那么和Min
相邻的元素肯定在后面的桶中,那么他们的差值肯定大于gap。
如果第n - 1
个桶没有放置元素,那么相当于n - 2
个元素放在了前面n - 2
个桶中,要么有一个空桶,要么每个桶恰好有一个元素。如果有一个空桶,那么前面一个有元素的桶的最大值和后面一个有元素的桶最小值在原数组中是连续的并且差值大于gap
,而同一个桶内的元素差值不大于gap
。如果没有空桶,由于每个桶内只有一个元素,那么相邻元素的最大值依旧是在两个相邻的桶之间比较。
基于上述分析,我们知道相邻两个元素的差值最大值肯定不是在同一个桶中,必定在相邻的桶中。所以我们只需要记录每一个桶的最大值和最小值,比较当前桶的最小值和上一个桶的最大值之间的差值即可。
C++ 代码
class Solution {
public:
struct bucket
{
int Min = INT_MAX,Max = INT_MIN;
bool used = false;
bucket(){}
};
int maximumGap(vector<int>& nums) {
int n = nums.size(),Max = INT_MIN,Min = INT_MAX;
if(n < 2) return 0;
for(int i = 0 ; i < n ; i ++)
{
Max = max(Max,nums[i]);
Min = min(Min,nums[i]);
}
int bucketSize = max(1,(Max - Min) / (n - 1));
int bucketNum = (Max - Min) / bucketSize + 1;
vector<bucket> buckets(bucketNum);
for(int i = 0 ; i < n ; i ++)
{
int idx = (nums[i] - Min) / bucketSize;
buckets[idx].used = true;
buckets[idx].Min = min(buckets[idx].Min,nums[i]);
buckets[idx].Max = max(buckets[idx].Max,nums[i]);
}
long long preBucketMax = Min,res = 0;
for(int i = 0 ; i < bucketNum ; i ++)
{
if(!buckets[i].used)
continue;
res = max(res,buckets[i].Min - preBucketMax);
preBucketMax = buckets[i].Max;
}
return res;
}
};
ceil(n/k) = floor((n+k-1)/k) = (n + k - 1) / k
感觉题解和代码的做法有点出入,题解里面写用ceil上取整但是代码里面好像用的是下取整