Difference between revisions of "TADM2E 4.6"
From Algorithm Wiki
(Recovering wiki) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
One more approach to solve the above problem | One more approach to solve the above problem | ||
| − | + | <pre> | |
1. Sort S1; (n log n) | 1. Sort S1; (n log n) | ||
2. Sort S2; (n log n) | 2. Sort S2; (n log n) | ||
3. beg := S1[0] | 3. beg := S1[0] | ||
end := S2[m-1] | end := S2[m-1] | ||
| − | 4. while (beg | + | 4. while (beg < n && end >=0 ) O(n) |
| − | if S1[beg] + S2[end] | + | if S1[beg] + S2[end] > sum then end-- |
| − | else if S1[beg] + S2[end] | + | else if S1[beg] + S2[end] < sum beg++ |
else return (beg, end) | else return (beg, end) | ||
End Loop | End Loop | ||
Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n) | Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n) | ||
| − | + | </pre> | |
--[[User:Max|Max]] 07:04, 25 June 2010 (EDT) | --[[User:Max|Max]] 07:04, 25 June 2010 (EDT) | ||
A third approach | A third approach | ||
| − | + | <pre> | |
1. Sort S1; O(n log n) | 1. Sort S1; O(n log n) | ||
2. for i=0 to n-1 | 2. for i=0 to n-1 | ||
| Line 25: | Line 25: | ||
return (val, S2[i]) | return (val, S2[i]) | ||
End Loop | End Loop | ||
| − | + | </pre> | |
Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n) | Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n) | ||
| + | |||
| + | ---- | ||
| + | There is also a linear solution, O(n). | ||
| + | <pre> | ||
| + | For i in 1..n | ||
| + | Check if x - S1[i] exists in seen numbers set T. | ||
| + | Return true or add S1[i] to T. | ||
| + | Check if x - S2[i] exists in T. | ||
| + | Return true or add S2[i] to T. | ||
| + | Return false | ||
| + | </pre> | ||
Latest revision as of 18:57, 28 November 2018
subtract n from the first set, sort both sets in O(nlogn). find the first equal under n
One more approach to solve the above problem
1. Sort S1; (n log n)
2. Sort S2; (n log n)
3. beg := S1[0]
end := S2[m-1]
4. while (beg < n && end >=0 ) O(n)
if S1[beg] + S2[end] > sum then end--
else if S1[beg] + S2[end] < sum beg++
else return (beg, end)
End Loop
Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)
--Max 07:04, 25 June 2010 (EDT)
A third approach
1. Sort S1; O(n log n)
2. for i=0 to n-1
val := x - S2[i]
if binary_search(S1, val) O(log n)
return (val, S2[i])
End Loop
Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)
There is also a linear solution, O(n).
For i in 1..n
Check if x - S1[i] exists in seen numbers set T.
Return true or add S1[i] to T.
Check if x - S2[i] exists in T.
Return true or add S2[i] to T.
Return false
