Description:
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. so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.
Example
Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.
Note
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Challenge
Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.
Solution:
class Solution {
public:
/**
* @param nums: a vector of integers
* @return: the maximum difference
*/
int maximumGap(vector<int> nums) {
auto sz = (int)nums.size();
if (sz <= 1) return 0;
int maxn = nums[0];
int minn = nums[0];
for (int i = 1; i < sz; ++i) {
maxn = max(maxn, nums[i]);
minn = min(minn, nums[i]);
}
int bucketSize = (maxn-minn) / sz + 1;
// int bucketSize = max((maxn-minn)/(sz-1), 1)
int bucketNum = (maxn-minn) / bucketSize + 1;
vector<int> maxBuckets(bucketNum, -1);
vector<int> minBuckets(bucketNum, maxn);
for (auto& e : nums) {
auto ind = (e-minn)/bucketSize;
maxBuckets[ind] = max(maxBuckets[ind], e);
minBuckets[ind] = min(minBuckets[ind], e);
}
int rc = 0;
int i = 0;
while (i < bucketNum && maxBuckets[i] == -1) ++i;
int pre = maxBuckets[i];
while (i < bucketNum) {
while (i < bucketNum && maxBuckets[i] == -1) ++i;
if (i < bucketNum) {
rc = max(rc, minBuckets[i]-pre);
pre = maxBuckets[i];
++i;
}
}
return rc;
}
};
转载于:https://www.cnblogs.com/deofly/p/maximum-gap.html
相关资源：JAVA上百实例源码以及开源项目
