找到兩個整數數組中最長的交集

我有這個問題，但不知道什麼是解決時間複雜度和空間複雜度的最佳方法。假設我有兩個整型數組找到兩個整數數組中最長的交集

a={1,2,3,4,5} 
    b={2,3,4,5,6}

，當然他們不一定進行排序。

所以問題是如何找到2,3,4,5？有一些代碼更好。在此先感謝

來源

2011-10-19 user899628

確實有更好的代碼！ –

如果數組未被排序，您可以詳細闡述一下您的需求：它應該返回最長的排序交叉點嗎？ – Bringer128

請編輯您的問題，並在文本中提供明確的問題陳述和/或在文本中包含更多示例，並提供答案;例如對於a = {1,2,3,4,5}，b = {2,3,1,4,5,6}以及對於a = {1,3,7,5,13,13} ，b = {2,13,7,1,4,5,13}。 –

這實際上是一個非常流行的編程問題。有一個動態的編程方法來解決它。您可以查看更多關於它的信息http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

來源

2011-10-19 03:12:19 jeff

我們爲什麼需要DP？問題說找到最長的交點，不是任何交點。我錯過了一點？

有很多解決方案。

int [] a = {...}; // n elements 
int [] b = {...}; // m elements

可以存儲在字典中，併爲其他陣列中檢查字典中的每個元素的一個陣列。那O(n)。由於字典的緣故，這將花費更多的空間。並且它不在原地

另一種解決方案是針對a中的每個元素，您可以對b進行線性搜索。這是O(n.m)

另一個是;如果你排序兩個陣列。然後對於一個數組中的每個元素在另一個數組中執行二進制搜索。你會發現兩個交點。這將是mlogn + nlogn或nlogm + mlogm

我們真的需要DP嗎？

來源

2011-10-19 03:35:09 DarthVader

我希望這個鏈接能夠解決您的問題。您必須編寫一個常用函數，它將在兩個數組中顯示常用數字。它只使用一個用於循環。這就是爲什麼它的複雜性將只是O（N）。

Find common numbers.

代碼在C。但我希望你能理解這個邏輯。

來源

2011-10-19 03:42:33 vikiiii

首先我們應該排序我們的數組，然後我們應該使用二進制搜索來找到這個數組的交集。爲什麼？因爲如果我們單獨搜索交叉點，沒有排序，我們的算法繁瑣將是N^2，但是如果我們在搜索之前排序數組，總共我們將有[log_2(N)N + (N(log_2(N)) up to N^2)]。我的方法對於大多數樣本很有用

來源

2011-10-19 03:45:36

找到兩個整數數組中最長的交集

回答

相關問題