陣列算法問題

如果我有兩個arrays.For例如，一個陣列是int[] one={1,2,4,6,54,3,34};另一個是int[] two={12,1,2,4,7,8,54,3,34,5}; 問題是我怎麼能得到一到兩個「相同的部件」。「示例中的相同部分」是[1,2,4]和[54,3,34]。陣列算法問題

P.S.您可以使用僞語言，c，c＃，java，php或其他語言。

P.S.現在我明確同樣的 parts.the相同的零件元素有的名單。

PSI有改變的例子，數組中的每一項的值不等於（你可以看到我的例子。）

至少兩項產品匹配
的兩個數組中匹配項的索引不必與匹配，但相同的部分必須連續。

來源

2011-04-30 Alex

這是什麼編程語言？你能否詳細說明「獲取相同的部分」？ – Hubro 2011-04-30 16:15:09

所以你正在尋找在兩個陣列中相同序列中的相似項目組？單獨的物品呢？這些組必須具有相同的索引才能匹配嗎？ – 2011-04-30 16:15:26

預期產量是多少？ – Davidann 2011-04-30 16:15:29

這可能是longest common subsequence問題。

來源

2011-04-30 16:17:17

對不起，這不是一個問題。但它激勵了我。 – Alex 2011-04-30 16:45:26

他尋求一個「最大公共子串」，這是不同的（並且更容易） – akappa 2011-04-30 17:08:08

您可以爲兩個數組構建一個suffix tree（看作'字符串'）並比較兩棵樹。

特別是，您可以選擇兩棵樹中的一棵（與較小數組關聯的那棵樹）（稱爲A）並開始遍歷它，模仿另一棵樹上的移動（稱爲B）。

如果您在樹A的節點u中，並且無法從此節點複製任何「移動」到樹B的相應樹上，則您找到了「最大匹配」（拼寫爲根到你），你可以修剪樹根A的子樹。

這只是一個想法，你必須建立它;注意你可以在O（n）中建立一個後綴樹，這種「相似性」也是O（n），所以它看起來是最優的。

來源

2011-04-30 17:05:09 akappa

http://en.wikipedia.org/wiki/Longest_common_substring_problem – hugomg 2011-05-01 17:03:59

不錯，我不知道這是一個衆所周知的問題。原則上，解決方案與我的解決方案沒有多大差別（我的解決方案中的節點「u」是「最深的內部節點，它具有來自其下的子樹中所有字符串的葉節點」）。當然，「維基百科」解決方案更清潔，所以我會實施它，而不是在兩棵樹上進行「互模擬」。 – akappa 2011-05-01 21:18:15

幾乎有一些優化的蠻力。最壞情況O（n^4）。 n是較短陣列的大小。

one=[1,2,4,6,54,3,34] 
two=[12,2,4,3,54,3,5] 
one_pos_list_map = {} # map of value -> position list 
one_pos_map = {} # map of value -> map of position -> 1 
for pos in xrange(len(one)): 
    val = one[pos] 
    if val not in one_pos_map: 
    one_pos_map[val] = {} 
    one_pos_map[val][pos] = 1 
    if val not in one_pos_list_map: 
    one_pos_list_map[val] = [] 
    one_pos_list_map[val].append(pos) 

checked = [False for i in xrange(len(two)*len(two))] 
def print_maximal_matches(start, end): 
    idx = start * len(two) + end - 1 
    if (checked[idx] or end - start < 2): 
    return 
    checked[idx] = True 
    match_pos_list = one_pos_list_map.get(two[start], []) 
    for match_pos in match_pos_list: 
    found = True 
    for i in xrange(start + 1, end): 
     if not one_pos_map.get(two[i], {}).get(match_pos + i - start, None): 
     found = False 
     break 
    if found: 
     print two[start:end] 
     return 

    print_maximal_matches(start + 1, end) 
    print_maximal_matches(start, end - 1) 

print_maximal_matches(0, len(two))

來源

2011-04-30 17:59:02 tarkeshwar

陣列算法問題

回答

相關問題