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.
------------------------------------------------------------------------------
reference
use n - 1 buckets
注意 bucketSize用double
class Solution {
public:
int maximumGap(vector<int> &num) {
if (num.size() < 2) return 0;
int min_val = num[0];
int max_val = num[0];
for (int i = 1; i < num.size(); i++) {
min_val = min(num[i],min_val);
max_val = max(num[i],max_val);
}
double bucketSize = (max_val - min_val) * 1.0 / (num.size() - 1);
vector<int> maxBucket(num.size() - 1, -1);
vector<int> minBucket(num.size() - 1, INT_MAX);
for (int i = 0; i < num.size(); i++) {
if (num[i] == min_val || num[i] == max_val) continue;
int bucket = (int)((num[i] - min_val) / bucketSize);
maxBucket[bucket] = max(num[i],maxBucket[bucket]);
minBucket[bucket] = min(num[i],minBucket[bucket]);
}
int maxGap = INT_MIN;
int preMax = min_val;
for (int i = 0; i < num.size() - 1; i++) {
if (maxBucket[i] == -1) continue;
maxGap = max(maxGap,minBucket[i] - preMax);
preMax = maxBucket[i];
}
maxGap = max(maxGap,max_val - preMax);
return maxGap;
}
};
Update Feb-18-2015radix sort
class Solution {
public:
int maximumGap(vector<int> &num) {
if (num.size() < 2) return 0;
vector<int> one;
vector<int> zero;
for (int i = 0; i < 32; i++) {
int mask = 1 << i;
for (int j = 0; j < num.size(); j++) {
if (num[j] & mask) {
one.push_back(num[j]);
}else {
zero.push_back(num[j]);
}
}
zero.insert(zero.end(),one.begin(),one.end());
num =zero;
one.clear();
zero.clear();
}
int maxGap = 0;
for (int i = 1; i < num.size(); i++) {
maxGap = max(num[i] - num[i - 1],maxGap);
}
return maxGap;
}
};
if (num[j] & mask) 判断的是0或者是非0，而不是1或0
radix sort, 10-base
REF
class Solution {
public:
int getMax(vector<int> &nums) {
int maxNum = 0;
for (int i = 0; i < nums.size(); i++) {
maxNum = max(nums[i],maxNum);
}
return maxNum;
}
void countSort(vector<int>& nums, int m) {
vector<int> count(10,0);
for (int i = 0; i < nums.size(); i++) {
count[(nums[i] / m) % 10]++;
}
// calculate start point for each key
int total = 0;
for (int i = 0; i < 10; i++) {
int oldCount = count[i];
count[i] = total;
total += oldCount;
}
// sort
vector<int> rt(nums.size());
for (int i = 0; i < nums.size(); i++) {
rt[count[(nums[i] / m) % 10]] = nums[i];
count[(nums[i] / m) % 10]++;
}
nums = rt;
}
int maximumGap(vector<int>& nums) {
int maxNumber = getMax(nums);
for (int m = 1; m <= maxNumber; m *= 10) {
countSort(nums,m);
}
int maxGap = 0;
for (int i = 1; i < nums.size(); i++) {
maxGap = max(maxGap,nums[i] - nums[i - 1]);
}
return maxGap;
}
};
