TADM2E 4.6 - Revision history

Jifalops at 18:57, 28 November 2018

2018-11-28T18:57:09Z

Jifalops at 18:56, 28 November 2018

2018-11-28T18:56:32Z

Algowikiadmin: Recovering wiki

2014-09-11T18:23:12Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:43Z

Recovering wiki

New page

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
<pre>
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)
</pre>
--[[User:Max|Max]] 07:04, 25 June 2010 (EDT)

A third approach
<pre>
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
</pre>

Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)

@@ Line 33: / Line 33: @@
 <pre>
 For i in 1..n
-   Check if x-S1[i] exists in seen numbers set T.
+   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.
+   Check if x - S2[i] exists in T.
      Return true or add S2[i] to T.
 Return false
 </pre>

← Older revision		Revision as of 18:56, 28 November 2018
Line 28:		Line 28:

	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>

@@ Line 2: / Line 2: @@
 One more approach to solve the above problem
-&lt;pre&gt;
+<pre>
 . Sort S1; (n log n)
 . Sort S2; (n log n)
 . beg := S1[0]
     end := S2[m-1]
-. while (beg &lt; n &amp;&amp; end &gt;=0 ) O(n)
+. while (beg < n && end >=0 ) O(n)
-       if S1[beg] + S2[end] &gt; sum then end--
+       if S1[beg] + S2[end] > sum then end--
-       else if S1[beg] + S2[end] &lt; sum  beg++
+       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)
-&lt;/pre&gt;
+</pre>
 --[[User:Max|Max]] 07:04, 25 June 2010 (EDT)
 A third approach
-&lt;pre&gt;
+<pre>
 . Sort S1; O(n log n)
 . for i=0 to n-1
@@ Line 25: / Line 25: @@
           return (val, S2[i])
     End Loop
-&lt;/pre&gt;
+</pre>
 Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)