如何比較O（n）中2個堆棧中的整數？

-3

我有兩個堆棧s1和s2。 s1包含負整數，s2包含正整數。這兩個堆棧已經從最低值（底部）到最高（頂部）排序。 x1和x2是s1和s2中的整數。我想檢查兩個堆棧以查看[x1 + x2 =給定的整數i]。在O（n）中做到這一點的最好方式（或方法）是什麼？如何比較O（n）中2個堆棧中的整數？

更新：X1和X2 integers..sorry

更新2：該方法返回一個布爾值，並且會對這些參數：

boolean method(Stack s1, Stack s2, int i)

方法將返回true，如果任何整數X1在s1 + s2中的任何整數x2 = i

2011-06-23 Loolooii

如何將兩個整數堆棧以一種整數形式相加？ –

只要通過這兩個堆棧並檢查？但那會是O（n^2）對嗎？ – Loolooii

你的意思是說如果在S1中有x1，在S2中是x2，那麼x1 + x2 =給定的整數？ – amit

我假設你是指s1中的任何數字+ s2中的任何數字都是給定的整數i。

如果是這樣，

爆開兩個頂部堆疊
加入他們
他們是否等於我
1. 是 - >完成後
是它比我大嗎？
1. YES - >然後，負號可以具有沒有對應的，把它扔掉，從S1彈出斷下負數，轉到2
2. NO - >然後，在正數可以具有沒有對應的，把它扔掉，突然開來s2的下一個正數，轉到2

（在任何時候，如果堆棧是空的，你做 - 沒有答案）

編輯：根據您的排序順序，我認爲我在第4步時錯了 - 但這個基本想法應該是閉幕的即

2011-06-23 20:27:14

這不會給你正確的答案，你可以從堆棧中彈出值，仍然可以與其他值進行良好組合。 – Peter

@peer，堆棧中的值已被排序。所以這不是問題。 – Loolooii

@Nima - 嘗試以下堆棧：1 2 3 4 5 10 16/-14 -13 -12 -9 -5 -4 -3和i = 5 10 + -5 = 5但是您不會從算法添加額外的堆棧將有助於保留其中一個堆棧的值 – Peter

回答