Maximum Gap
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
------------------------ thinking -------------------------------------
https://oj.leetcode.com/discuss/19100/o-n-c-solution-in-20ms-and-explanation
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.
Analysis written by @porker2008.
--------------------------- codes --------------------------------------------
class Solution {
public:
int maximumGap(vector<int> &num) {
if (num.size() < 2) {
return 0;
}
vector<int> grids;
grids.reserve(num.size() * 2);
vector<bool> mark(num.size(), false);
int min = num[0];
int max = num[0];
for (int i = 1; i < num.size(); i++) {
if (num[i] > max) {
max = num[i];
}
if (num[i] < min) {
min = num[i];
}
}
//important to have 0.1 added to max, or the max value will get num.size() as the index, which will cause the problem
double gap = double(max + 0.1 - min) / num.size();
for (int i = 0; i < num.size(); i++) {
int index = (num[i] - min) / gap;
if (mark[index] == false) {
mark[index] = true;
grids[index * 2] = num[i];
grids[index * 2 + 1] = num[i];
} else {
if (num[i] < grids[index * 2]) {
grids[index * 2] = num[i];
}
if (num[i] > grids[index * 2 + 1]) {
grids[index * 2 + 1] = num[i];
}
}
}
int maxGap = 0;
for (int i = 0; i < num.size(); i++) {
if (mark[i] && (grids[i * 2 + 1] - grids[i * 2] > maxGap)){
maxGap = grids[i * 2 + 1] - grids[i * 2];
}
}
int start = 0;
int end = 1;
while (true) {
while (end < num.size() && !mark[end]) {
end++;
}
if (end >= num.size()) {
break;
} else {
maxGap = (grids[end * 2] - grids[start * 2 + 1]) > maxGap? grids[end * 2] - grids[start * 2 + 1] : maxGap;
start = end;
end++;
}
}
return maxGap;
}
};
No comments:
Post a Comment