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.

 

int maximumGap(vector &num) {

if (num.size() < 2) return 0;
int minVal=INT_MAX,maxVal=-1,local_min=INT_MIN,local_max=-1;
int size=num.size();

vector::iterator it;

//get the max and min value
for( it=num.begin() ; it!=num.end();it++)
{
if(*it < minVal) { minVal=*it; } if(*it >maxVal)
{
maxVal=*it;
}
}

//Slot Size is the number of elements in each bucket

int slotsSize= (maxVal-minVal)/(size-1);

//total number of buckets
int numbuckets=(maxVal-minVal)/slotsSize;

//pair is used for max and min
vector<pair<int, int> > buckets(numbuckets, make_pair(-1, -1));

// assign max and min for each bucket
for( it=num.begin() ; it!=num.end();it++)
{
int val=*it;
int bucketNum=(val-(minVal+1))/slotsSize;
if(val != minVal && val !=maxVal)
{
if (buckets[bucketNum].first == -1)
buckets[bucketNum].first = val;
else
buckets[bucketNum].first = min(buckets[bucketNum].first, val);
buckets[bucketNum].second = max(buckets[bucketNum].second, val);
}

}
int max_diff=0;
bool first_time=true;
for(int i=0 ; i < numbuckets;i++) { if(i==numbuckets-1 ) { int x=i; while(buckets[x].first == -1) { x–; } int temp_max=buckets[x].second; if((maxVal- temp_max ) > max_diff)
max_diff=maxVal- temp_max;
break;
}

if(buckets[i].first != -1)
{
if(first_time)
{
int temp_min=buckets[i].first;
if((temp_min – minVal) >max_diff)
max_diff=temp_min – minVal;
first_time=false;
}

for(int j=i+1 ; j <numbuckets;j++) { // If next bucket is non empty if(buckets[j].first != -1) { int temp_max=buckets[i].second; int temp_min=buckets[j].first; if((temp_min – temp_max) >max_diff)
max_diff=temp_min – temp_max;
break;
}
}
}
}
return max_diff;
}

 

An alternative to above solution:(c++ 11)

http://www.cnblogs.com/skysand/p/4179099.html

Leave a Reply

Your email address will not be published. Required fields are marked *