發現重複號碼

的重複，這是我的算法，我與我的朋友（這是在計算器網站）寫它這種算法會發現只是第一個重複的數量和O(n) 返回it.this作品我想完成這個算法，幫助我獲得重複的重複號碼。考慮我有[1,1,3,0,5,1,5] 我想這個算法返回2重複數字是1 and 5與他們的重複，分別是3 and 2.how我可以這樣做與O(n)？發現重複號碼

1 Algorithm Duplicate(arr[1:n],n) 
2 
3 { 
4  Set s = new HashSet();i:=0; 
5  while i<a.size() do 
6  { 
7   if(!s.add(a[i)) then 
8   { 
9    return a[i]; //this is a duplicate value! 
10   break; 
11   } 
12   i++; 
13  } 
14 }

來源

2010-11-20 user472221

你可以在Java中做到這一點：

List<Integer> num=Arrays.asList(1,1,1,2,3,3,4,5,5,5); 
    Map<Integer,Integer> countNum=new HashMap<Integer, Integer>(); 
    for(int n:num) 
    { 
     Integer nu; 
     if((nu=countNum.get(n))==null) 
     { 
      countNum.put(n,1); 
      continue; 
     } 
     countNum.put(n,nu+1); 
    }

每次得到重複最好是將計在地圖中的數

不是迭代的。

來源

2010-11-20 07:13:16 Emil

謝謝所以你的算法將是O（n）？ – user472221 2010-11-20 08:10:08

是的，它只是一個循環。 – Emil 2010-11-20 08:23:35

在此先感謝 – user472221 2010-11-20 19:03:01

使用地圖/詞典的數據結構。
迭代列表。
對於列表中的每個項目，請執行地圖查找。如果鍵（項目）存在，則增加其值。如果密鑰不存在，請插入密鑰和初始計數。

來源

2010-11-20 06:46:58 dteoh

你能寫出你的算法真的很難得到我初學者在算法中預先感謝 – user472221 2010-11-20 06:51:26

也是O（n^2）我是吧？ – user472221 2010-11-20 07:20:41

@ user472221：對於插入，刪除和查找，可變「Map」和「Dictionary」數據結構通常具有「Θ（1）」的分期最壞步驟複雜度。因此，@ suihock建議的總分攤最壞步驟複雜度將爲'Θ（n）'。 – 2010-11-20 13:10:41

在這個特殊的例子中，它並沒有太多的關於算法，它是關於數據結構：Multiset就像Set，除了它不僅存儲唯一的項目，而且它存儲每個項目的頻率在Multiset。基本上，Set告訴你一個特定的項目是否在Set在所有，另外一個Multiset還告訴您多久該特定產品在Multiset。

所以，基本上所有你需要做的就是從Array構建一個Multiset。這裏有一個Ruby的例子：

require 'multiset' 

print Multiset[1,1,3,0,5,1,5]

是的，就是這樣。這將打印：

如果你只是想實際副本，您只需delete與計數的項目少於2：

print Multiset[1,1,3,0,5,1,5].delete_with {|item, count| count < 2 }

這只是打印

#1 3 
#2 5

由於@suihock提到，您也可以使用Map，這基本上意味着代替Multiset負責元素計數你，你要自己做：

m = [1,1,3,0,5,1,5].reduce(Hash.new(0)) {|map, item| map.tap { map[item] += 1 }} 
print m 
# { 1 => 3, 3 => 1, 0 => 1, 5 => 2 }

同樣，如果你只希望重複：

print m.select {|item, count| count > 1 } 
# { 1 => 3, 5 => 2 }

但你可以有一個更容易，如果不是自己的計算，可以使用Enumerable#group_by到組元素，然後將這些分組映射到它們的大小。最後，轉換回Hash：

print Hash[[1,1,3,0,5,1,5].group_by(&->x{x}).map {|n, ns| [n, ns.size] }] 
# { 1 => 3, 3 => 1, 0 => 1, 5 => 2 }

所有這些都Θ（N）的攤銷最壞情況下的步驟的複雜性。

來源

2010-11-20 13:04:39

發現重複號碼

回答

相關問題