LeetCode Q164: Maximum Gap (hard)

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.

Solution:
Radix sort!!!

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size()<2)
	return 0;
	int maxv=nums[0];
	for(int i=0; i<nums.size(); i++)
	maxv=max(nums[i], maxv);
	int k=1; // total k digits in maxv.
	while(true)
	if(maxv/int(pow(10, k++))==0)
	break;
	k=k-1;
	vector<vector<int> > myBucketPre(10);
	vector<vector<int> > myBucketCur(10);
	for(int i=0; i<k; i++){
	for(int j=0; j<10; j++)
	myBucketCur[j].clear();
	if(i==0){
	for(int j=0; j<nums.size(); j++){
	myBucketPre[nums[j]%int(pow(10, i+1))].push_back(nums[j]);
	}
	continue;
	}else{
	for(int j=0; j<10; j++){
	for(int q=0; q<myBucketPre[j].size(); q++){
	int num=myBucketPre[j][q];
	int tmpnum=num/int(pow(10, i));
	myBucketCur[tmpnum%10].push_back(num);
	}
	}
	}
	myBucketPre=myBucketCur;
	}
	int gap=0;
	int pre=-1;
	int cur=-1;
	for(int j=0; j<10; j++){
	for(int q=0; q<myBucketPre[j].size(); q++){
	cur=myBucketPre[j][q];
	if(pre==-1){
	pre=cur;
	continue;
	}
	gap=max(gap, cur-pre);
	pre=cur;
	}
	}
	return gap;
	}
	};

view raw Q164.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size()<2)
	return 0;
	vector<vector<int> > preBucket(10);
	vector<vector<int> > curBucket(10);
	vector<int> curNums;
	for(int i=0; i<32; i++){
	curNums.clear();
	if(i==0)
	curNums=nums;
	else{
	for(int j=0; j<10; j++){
	for(int k=0; k<preBucket[j].size(); k++)
	curNums.push_back(preBucket[j][k]);
	}
	}
	for(int j=0; j<curNums.size(); j++){
	int d = (curNums[j]/int(pow(10, i)))%10;
	curBucket[d].push_back(curNums[j]);
	}
	preBucket=curBucket;
	curBucket.clear();
	curBucket.resize(10);
	}
	int res=0;
	for(int j=1; j<curNums.size(); j++)
	res=max(res, curNums[j]-curNums[j-1]);
	return res;
	}
	};

view raw Q164Rnd2.cpp hosted with ❤ by GitHub

Rnd3 sol:

	class Solution {
	public:
	int maximumGap(vector<int>& nums) {
	if(nums.size()<2)
	return 0;
	vector<vector<int> > curBucket(10);
	vector<int> curNums=nums;
	for(int i=0; i<32; i++){
	for(int j=0; j<curNums.size(); j++){
	int d = (curNums[j]/int(pow(10, i)))%10;
	curBucket[d].push_back(curNums[j]);
	}
	curNums.clear();
	for(int j=0; j<10; j++){
	for(int k=0; k<curBucket[j].size(); k++)
	curNums.push_back(curBucket[j][k]);
	}
	curBucket.clear();
	curBucket.resize(10);
	}
	int res=0;
	for(int j=1; j<curNums.size(); j++)
	res=max(res, curNums[j]-curNums[j-1]);
	return res;
	}
	};

view raw Q164Rnd3.cpp hosted with ❤ by GitHub