// O(n) solution using binning
findClose(int n, double A[n])
{
// Find min and max
min = max = A[0];
for(i = 1; i < n; ++i)
{
if (A[i] > max) max = A[i];
if (A[i] < min) min = A[i];
}
// Set up bins
int bins = n-1;
double binWidth = (max - min) / bins;
double binTable[bins] = {min-1.0};
// Now any two elements falling into same hash bin are close
// In addition, it is necessary to check the adjacent bins to see if
a close value is there
for(i = 0; i < n; ++i)
{
// Determine which bin the value falls into
binIndex = (A[i] - min) / binWidth;
// If there is already a value there, the two values are close
if (binTable[binIndex] >= min)
{
result = (A[i], binTable[binIndex]);
break;
}
// Check the next lower bin
if ((binIndex > 0) and (binTable[binIndex-1] >= min))
{
if ((A[i] - binTable[binIndex-1]) < binWidth)
{
result = (A[i], binTable[binIndex-1]);
break;
}
}
// Check the next higher bin
if ((binIndex+1 < bins) and (binTable[binIndex+1] >= min))
{
if ((binTable[binIndex+1] - A[i]) < binWidth)
{
result = (A[i], binTable[binIndex+1]);
break;
}
}
// Store value in the bin
binTable[binIndex] = A[i];
}
}
On Apr 1, 7:32 am, snehal jain <[email protected]> wrote:
> For a set S of n real numbers, a pair of elements x, y belong to S,
> where x < y, are said to be close if
> y – x <= ( max(S) – min(S) ) / (n-1)
> Suppose you are given an unsorted array A[1 : n] of distinct real
> numbers. Design an algorithm that finds a pair of close numbers in A
> in O(n) time.
>
> my solutions
>
> 1. brute force: complexity n2
> 2. sort the array.
> take 2 ptrspt1 and pt2.initially pt1 points to 1st elementand pt2 pts
> to 2nd element. check if they are close nos.
>
> case1; if they r closeincrement pt2. and again check. repeat this
> until u find close pairs. when pt1and pt2 doesnt pt to close pairat
> this point all elements b/w pt1 and pt2 are also close. increment
> close_pair_count accordingly, check if element jst b4 pt2 and at pt2
> are also close.
>
> case 2: increment both pt1and pt2 and continue
>
> repeat above steps til u reach end of array..
>
> m unable to think linear algo.please help..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
