Difference between revisions of "TADM2E 4.8"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
(a): | (a): | ||
| − | + | <pre> | |
Sort S with any nlogn sorting method of your choice. | Sort S with any nlogn sorting method of your choice. | ||
| − | for( int i = 1; i | + | for( int i = 1; i <= n; ++i ) |
{ | { | ||
int j = x - S[i]; | int j = x - S[i]; | ||
Binary search for j in the sub-array of S[i+1~n] and close the problem once it's been found; | Binary search for j in the sub-array of S[i+1~n] and close the problem once it's been found; | ||
} | } | ||
| − | + | </pre> | |
(b): | (b): | ||
| − | + | <pre> | |
Subtract each of S[1~n] from x to get a new array of real numbers T[1~n]. | Subtract each of S[1~n] from x to get a new array of real numbers T[1~n]. | ||
int i = 1, j = 1; | int i = 1, j = 1; | ||
| − | while( i | + | while( i <=n && j <= n ) |
{ | { | ||
if( S[i] == T[j] ) | if( S[i] == T[j] ) | ||
| Line 21: | Line 21: | ||
else | else | ||
{ | { | ||
| − | S[i] | + | S[i] < T[j] ? ++i : ++j; |
} | } | ||
} | } | ||
| − | + | </pre> | |
Another Solution to part B without creating the additional Array.. | Another Solution to part B without creating the additional Array.. | ||
| − | + | <pre> | |
i = 0; | i = 0; | ||
j = n - 1; | j = n - 1; | ||
| − | for (i = 0; i | + | for (i = 0; i < j; i++) |
{ | { | ||
| − | while( (i | + | while( (i < j) && (S[j] + S[i] > x ) |
{ j--; | { j--; | ||
} | } | ||
| Line 43: | Line 43: | ||
} | } | ||
| − | + | "i" scans from left to right, "j" from right to left, | |
looking for the right pair... | looking for the right pair... | ||
| − | + | </pre> | |
Revision as of 18:23, 11 September 2014
(a):
Sort S with any nlogn sorting method of your choice.
for( int i = 1; i <= n; ++i )
{
int j = x - S[i];
Binary search for j in the sub-array of S[i+1~n] and close the problem once it's been found;
}
(b):
Subtract each of S[1~n] from x to get a new array of real numbers T[1~n].
int i = 1, j = 1;
while( i <=n && j <= n )
{
if( S[i] == T[j] )
{
problem solved;
break;
}
else
{
S[i] < T[j] ? ++i : ++j;
}
}
Another Solution to part B without creating the additional Array..
i = 0;
j = n - 1;
for (i = 0; i < j; i++)
{
while( (i < j) && (S[j] + S[i] > x )
{ j--;
}
if (x == (S[j] + S[i])
{
return (S[i],S[j]);
break;
}
}
"i" scans from left to right, "j" from right to left,
looking for the right pair...
