首页 > 代码库 > leetcode[164] Maximum Gap
leetcode[164] Maximum Gap
梅西刚梅开二度，我也记一题。
在一个没排序的数组里，找出排序后的相邻数字的最大差值。
要求用线性时间和空间。
如果用nlgn的话，直接排序然后判断就可以了。so easy
class Solution {public: int maximumGap(vector<int> &num) { if (num.size() < 2) return 0; sort(num.begin(), num.end()); int maxm = -1; for (int i = 1; i < num.size(); i++) { if (abs(num[i] - num[i-1]) > maxm) maxm = abs(num[i] - num[i-1]); } return maxm; }};
但我们要的是线性时间。
其实这个思想在算法课上有讲过。用桶的思想。把数组分成几个桶，然后判断相邻桶的最大与最小之间的差值。关键是要知道每个桶的长度，已经桶的个数。
class Solution {public: int maximumGap(vector<int> &num) { if (num.size() < 2) return 0; int Max = num[0], Min = Max, ans = 0; for (int i = 1; i < num.size(); i++) { if (num[i] < Min) Min = num[i]; if (num[i] > Max) Max = num[i]; } if (Max == Min) return 0; int bucketGap = (Max - Min)/num.size() + 1; // 桶的间隔是关键 int bucketLen = (Max - Min)/bucketGap + 1; // 举个 1，2，3的例子就知道了 vector<int> MinMax(2, INT_MAX); MinMax[1] = INT_MIN; vector<vector<int> > bucket(bucketLen, MinMax); for (int i = 0; i < num.size(); i++) { int ind = (num[i] - Min)/bucketGap; if (num[i] < bucket[ind][0]) bucket[ind][0] = num[i]; if (num[i] > bucket[ind][1]) bucket[ind][1] = num[i]; } int first = bucket[0][1], second; for (int i = 1; i < bucketLen; i++) { if (bucket[i][0] == INT_MAX) continue; second = bucket[i][0]; int tmpmax = second - first; ans = tmpmax > ans ? tmpmax : ans; first = bucket[i][1]; } 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.
leetcode[164] Maximum Gap