Difference between revisions of "TADM2E 4.8"
From Algorithm Wiki
(Recovering wiki) |
m (Removed the extra break) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 33: | Line 33: | ||
for (i = 0; i < j; i++) | for (i = 0; i < j; i++) | ||
{ | { | ||
| − | while( (i < j) && (S[j] + S[i] > x ) | + | while( (i < j) && (S[j] + S[i] > x ) ) |
{ j--; | { j--; | ||
} | } | ||
| − | if (x == (S[j] + S[i]) | + | if (x == (S[j] + S[i]) ) |
{ | { | ||
| − | return | + | return true; |
| − | + | ||
} | } | ||
} | } | ||
| Line 45: | Line 45: | ||
"i" scans from left to right, "j" from right to left, | "i" scans from left to right, "j" from right to left, | ||
looking for the right pair... | looking for the right pair... | ||
| + | </pre> | ||
| + | |||
| + | Yet another solution to solve both parts in linear time using a hashtable. | ||
| + | <pre> | ||
| + | Initialize a hash-table backed dictionary D; // O(n*lg(n)) if the underlying structure is a BST. | ||
| + | for each e in S: | ||
| + | delta = x - e; | ||
| + | if Search(D, delta) is not NULL: | ||
| + | return (e, delta); | ||
| + | else | ||
| + | Insert(D, {e => delta}); // Insert a record with key e and value delta. | ||
</pre> | </pre> | ||
Latest revision as of 00:45, 22 March 2017
(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 true;
}
}
"i" scans from left to right, "j" from right to left,
looking for the right pair...
Yet another solution to solve both parts in linear time using a hashtable.
Initialize a hash-table backed dictionary D; // O(n*lg(n)) if the underlying structure is a BST.
for each e in S:
delta = x - e;
if Search(D, delta) is not NULL:
return (e, delta);
else
Insert(D, {e => delta}); // Insert a record with key e and value delta.
