leetcode[164] Maximum Gap

时间:2023-03-08 19:17:29

梅西刚梅开二度,我也记一题。

在一个没排序的数组里,找出排序后的相邻数字的最大差值。

要求用线性时间和空间。

如果用nlgn的话,直接排序然后判断就可以了。so easy

class Solution {
public:
int maximumGap(vector<int> &num) {
if (num.size() < ) return ;
sort(num.begin(), num.end());
int maxm = -;
for (int i = ; i < num.size(); i++)
{
if (abs(num[i] - num[i-]) > maxm)
maxm = abs(num[i] - num[i-]);
}
return maxm;
}
};

但我们要的是线性时间。

其实这个思想在算法课上有讲过。用桶的思想。把数组分成几个桶,然后判断相邻桶的最大与最小之间的差值。关键是要知道每个桶的长度,已经桶的个数。

class Solution {
public:
int maximumGap(vector<int> &num) {
if (num.size() < ) return ;
int Max = num[], Min = Max, ans = ;
for (int i = ; i < num.size(); i++)
{
if (num[i] < Min)
Min = num[i];
if (num[i] > Max)
Max = num[i];
}
if (Max == Min) return ; int bucketGap = (Max - Min)/num.size() + ; // 桶的间隔是关键
int bucketLen = (Max - Min)/bucketGap + ; // 举个 1,2,3的例子就知道了
vector<int> MinMax(, INT_MAX);
MinMax[] = INT_MIN;
vector<vector<int> > bucket(bucketLen, MinMax); for (int i = ; i < num.size(); i++)
{
int ind = (num[i] - Min)/bucketGap;
if (num[i] < bucket[ind][])
bucket[ind][] = num[i];
if (num[i] > bucket[ind][])
bucket[ind][] = num[i];
} int first = bucket[][], second;
for (int i = ; i < bucketLen; i++)
{
if (bucket[i][] == INT_MAX) continue;
second = bucket[i][];
int tmpmax = second - first;
ans = tmpmax > ans ? tmpmax : ans;
first = bucket[i][];
} return ans;
}
};

最后附上官网的解法说明:

Suppose there are N elements and they range from A to B.

Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)]

Let the length of a bucket to be len = ceiling[(B - A) / (N - 1)], then we will have at most num = (B - A) / len + 1 of bucket

for any number K in the array, we can easily find out which bucket it belongs by calculating loc = (K - A) / len and therefore maintain the maximum and minimum elements in each bucket.

Since the maximum difference between elements in the same buckets will be at most len - 1, so the final answer will not be taken from two elements in the same buckets.

For each non-empty buckets p, find the next non-empty buckets q, then q.min - p.max could be the potential answer to the question. Return the maximum of all those values.