如何將元素分配到兩個不同的集合中？

如果有兩套 -如何將元素分配到兩個不同的集合中？

set1 - [tag, boLD, Link] 
set2 - [BOLd, TAG, Badge, foo]

可能是什麼使元素對像的高效算法 -

pairs = [tag, TAG], [boLD, BOLd], [Link, null], [null, Badge], [null, foo]

通知配對的case-insensitive名稱的基礎上。

我想避免O（N^2），它反覆查找set1中的所有元素，並查看set2中的元素。

編輯：我認爲，如果我們可以用Ternary Search Tries，使符號表執行，其中鍵是設置1元，並從集2的值。 set2剩下的元素可以最後處理。

來源

2015-04-02 Prakhar

先顯示一些努力。 – Pratik 2015-04-02 12:21:08

爲什麼不告訴我們你到目前爲止的想法？好消息是：O（N^2）是最差情況的上限;-) – GhostCat 2015-04-02 12:21:10

作爲集不支持索引訪問所以不幸的是，你需要查找所有元素！ – 2015-04-02 12:23:27

你可以做到這一點在O(n)，如果您使用支持O(1)得到操作一些數據結構 - 例如HashMap。

HashMap<String, String> set1 = new HashMap<>(); 
    HashMap<String, String> set2 = new HashMap<>(); 
    class Pair{ 
     String str1; 
     String str2; 

     Pair(String s1, String s2){ 
      str1 = s1; 
      str2 = s2; 
     } 
    } 
    Set <Pair> pairs = new HashSet<>(); 
    set1.put("tag", "tag"); 
    set1.put("bold", "boLD"); 
    set1.put("link", "Link"); 
    set2.put("tag", "TAG"); 
    set2.put("bold", "BOLd"); 
    set2.put("badge", "Badge"); 
    set2.put("foo", "foo"); 

    for (String s : set1.keySet()){ 
     if (set2.containsKey(s)) 
      pairs.add(new Pair(set1.get(s), set2.get(s))); 
     else 
      pairs.add(new Pair(set1.get(s), null)); 
    } 

    for (String s : set2.keySet()){ 
     if (!set1.containsKey(s)) 
      pairs.add(new Pair(null, set2.get(s))); 
    } 

    for(Pair p : pairs) 
     System.out.println(p.str1 + " " + p.str2);

來源

2015-04-02 12:38:21

首先，我不會只打印它。我需要一個數據結構來返回，以及多個空條目如何在任何數據結構中作爲鍵存在。 – Prakhar 2015-04-02 12:51:26

您可以將值插入某些數據結構，而不是打印。看到我編輯的帖子。 – 2015-04-02 13:03:52

轉換爲小寫比寫出所有可能的案例身份排列更爲切實可行。 – 2015-04-02 23:06:37

你可以創建一個HashMap並遍歷這兩個數組。對於密鑰，您可以使用每個字符串的小寫形式。這應該給你線性的運行時複雜度，並且很容易實現。

來源

2015-04-02 12:37:31 timcbaoth

一個簡單的解決方案（在Python中給出，懶得寫信的Java），它是線性的列表的長度將是以下幾點：

map1 = {} 
for i,e in enumerate(set1): 
    s = e.lower() 
    map1[s] = i 

map2 = {} 
for i,e in enumerate(set2): 
    s = e.lower() 
    map2[s] = i 

pairs = [] 
for i,e in enumerate(set1): 
    s = e.lower() 
    if s in map2: 
     elem = (e, set2[map2[s]]) 
    else: 
     elem = (e, None) 
    pairs.append(elem) 

for i,e in enumerate(set2): 
    s = e.lower() 
    if s not in map1: 
     pairs.append((None, e))

我也假設有在輸入中沒有重複，也就是說，它匹配來自另一個集合的0或1個單詞，並且在每個集合中不存在具有不同情況的相同單詞，因爲我不確定您期望輸出的是什麼。

這可能不是最有效的方式去做，但總體上看起來很好，因爲它仍然是O（n）。

來源

2015-04-02 12:48:56

如何將元素分配到兩個不同的集合中？

回答

相關問題