確定有序數組之間的交集複雜度

Question

問題：給定兩個大小爲n的排序數組A []和B []，檢查它們是否有非空的相交（我不需要相交本身，只有決定）

解決方案：在B []中對A []的每個元素進行二進制排序得到一個O（n lg n）解。迭代每個數組從開始到結束（做一些非常類似於從Mergesort合併的東西）給出了O（n）解決方案。

我想知道是否有更好的（就複雜性而言）解決方案。我很確定沒有，但我一直在尋找「嘿，如果你給我一個更好的解決方案，我可以在o（n lg n）中排序一個向量，這是不可能的」 - 參數類型

Answer 1

再次閱讀問題 - "Given two sorted arrays ..."。

最初建議的排序是不需要的，這導致您到O(n)解決方案來執行類似合併分類的過程。

你不能做比合並類似的過程更好，記住如果找到交集，你可以提早停下來。

如果他們不排序：

A-基於散列的地圖解決方案在技術上是O(n) - 插入來自所有元素到一個哈希地圖（O(n)）。查找B中的每個元素（O(n)）。

對於排序解決方案，由於您只需要做出決定，因此只需要對A進行排序並循環遍歷B，對A中的每個元素執行O(log n)查找，並在找到某個項目後停止。你不會比O(n log n)做得更好，但如果比賽早期發現，你可以減少多達一半的工作。