查找跨多個數組的序列號的有效方法？

Question

我不找任何代碼或有東西給我正在做的。我需要一些幫助才能開始正確的方向，但不知道如何去做。如果有人能夠提供一些資源來解決這些問題，我將非常感激。我坐在我的筆記本上，無法設計一個可以做我想做的事情的算法。

我也許可以這樣做：

foreach element in array1 
    foreach element in array2 
     check if array1[i] == array2[j]+x 

我相信這會爲正向和反向序列工作，併爲倍數只檢查array1[i] % array2[j] == 0。我有一個包含INT數組列表，並且我得到list[index]（用於array1）和list[index+1]爲array2，但這種方法可以得到複雜和漫長的快，尤其是對於大型陣列和這些陣列的大名單。因此，我正在尋找更好的解決方案。


我試圖來爲不同陣列中找到序列號的算法。

例如：

[1, 5, 7]和[9, 2, 11]會發現，1和2是連續的。

這也應該適用於在多個陣列多個序列。因此，如果有第三個數組[24, 3, 15]，它也將包含該序列中的3，並繼續到下一個數組，直到沒有與last sequential element + 1匹配的數字。

還應該能夠找到陣列之間的多個序列。

例如：

[1, 5, 7]和[6, 3, 8]會發現，5和6是連續的，也7和8是連續的。

我也有興趣在尋找反向序列。

例如： [1, 5, 7]和[9, 4, 11]將返回5和4是相反順序。

實施例與所有：

[1, 5, 8, 11]和[2, 6, 7, 10]將返回1和2是連續的，5和6是連續的，8和7是相反順序，11和10是相反順序。

它也可以重疊：

[1, 5, 7, 9]和[2, 6, 11, 13]將返回1和2順序，5和6順序，也7和6反向順序。

我也想擴大這個與x差，以檢查數（上面的例子與1差量檢查）。

除了所有這些（雖然這可能是一個不同的問題），我也想檢查的倍數，

例子： [5, 7, 9]和[10, 27, 8]將返回5和10作爲倍數，9和27作爲倍數。

和數字相同的地方。

例子： [3, 5, 7]和[13, 23, 25]將返回3和13和23具有相同的個位數字。

Answer 1

使用的字典（組或散列映射）

dictionary1 = {} 

轉到通過每個項目的第一陣列中，並將其添加到詞典中。 [1, 5, 7]

現在dictionary1 = {1:true, 5:true, 7:true}

dictionary2 = {} 

現在經歷的每個項目在[6, 3, 8]和查找，如果它是一個序列的一部分。

6是一個序列的一部分，因爲dictionary1[6+1] == true 所以dictionary2[6] = true

我們得到了dictionary2 = {6:true, 8:true}

現在設置dictionary1 = dictionary2和dictionary2 = {}，並進入第三陣列..等等。

我們只跟蹤序列。 由於每個查找是O（1），並且我們每個數字有兩個查找（例如6-1和6 + 1），所以總數爲n * O（1），它是O（N）（N是所有數組中的數字）。

Answer 2

僞代碼中概述的蠻力方法將是O(c^n)（指數），其中c是每個陣列的平均元素數量，n是總數組的數量。

如果輸入空間稀疏（這意味着將有平均人失蹤人數比呈現數），然後以加快這一進程的一種方式是先創建所有單個有序集合所有的唯一編號你的不同陣列。這個「主」集將允許您提前退出（即循環中的break語句）任何不可行的序列。

例如，如果我們有輸入數組[1, 5, 7]和[6, 3, 8]和[9, 11, 2]，則主有序集合將是{1, 2, 3, 5, 6, 7, 8, 9, 11}。如果我們正在尋找n+1類型序列，我們可以跳過繼續檢查任何包含3或9或11的序列（因爲n+1的值不存在於有序集合中的下一個索引處。雖然加速並非劇烈在這個特定的例子中，如果你有幾百個輸入數組和很大的值範圍（稀疏性），那麼加速應該是指數級的，因爲你將能夠提前退出許多排列。如果輸入空間不稀疏（如在這個例子中，我們沒有太多的孔），將加速比將小於指數。

進一步的改進將是存儲「主」設置鍵值對，其中的關鍵是如上例所示的n值，並且該對的值部分是包含該值的任何數組的索引列表。前面例子的主集將是：{[1, 0], [2, 2], [3, 1], [5, 0], [6, 1], [7, 0], [8, 1], [9, 2], [11, 2]}。有了這種架構，掃描時間可能會低至O(c*n)，因爲您可以遍歷這個單一的有序序列，尋找有效的序列，而不是遍歷所有的子陣列。通過還要求數組索引增加，您可以清楚地看到，因爲數組的順序不正確，並且與2->3順序等相同，所以可以跳過該序列。注意，這個玩具示例有些過於簡化，因爲在實踐中您需要鍵值對的值部分的索引列表。如果在多個數組中出現相同的值n（重複值），這將是必要的。