從列表中刪除重複的元素，但只有那些有奇數重複的人

我想從列表中刪除重複的元素，其重複數是奇數。例如，對於下面的列表：[1, 2, 3, 3, 3, 5, 8, 1, 8]我有1個重複2次，3個重複3次，8個重複2次。所以，1和8應該出，而是3/3的元素我需要離開僅1從列表中刪除重複的元素，但只有那些有奇數重複的人

這是我想出了：

def remove_odd_duplicates(arr): 
    h = {} 
    for i in arr: 
     if i in h: 
      h[i] += 1 
     else: 
      h[i] = 1 

    arr = [] 
    for i in h: 
     if h[i] % 2: 
      arr.append(i) 

    return arr

它返回正確的一切：[2, 3, 5]，但我相信這可以用更好的方式寫出來。有任何想法嗎？

來源

2014-10-19 Salvador Dali

是否爲了事項？ – 2014-10-19 13:39:49

@AshwiniChaudhary命令並不重要，但複雜性是。在我的情況下，它是O（n），我不希望它惡化到O（n^2）與計數元素 – 2014-10-19 13:40:46

@SalvadorDali這種算法更像n log n，因爲反覆查找。最後的線性掃描並不顯着，呈現爲隱性。 – user3125280 2014-10-19 13:42:53

您可以使用collections.Counter和列表理解，這樣

data = [1, 2, 3, 3, 3, 5, 8, 1, 8] 
from collections import Counter 
print [item for item, count in Counter(data).items() if count % 2] 
# [2, 3, 5]

的Counter給出了一個解釋，與輸入迭代的密鑰和它們對應的計數的值，每一個元素。因此，我們遍歷該字典並檢查計數是否奇數，並僅過濾這些項目。

注意：該解決方案的複雜性仍然是O（N），就像您的原始程序一樣。

來源

2014-10-19 13:37:46 thefourtheye

你確定它仍然是O（n）嗎？因爲當我考慮這個解決方案時，我認爲它是O（n^2），因爲對於每個元素我需要計算這些元素的數量。而它的做法是通過迭代列表第二次，從而爆炸到O（n^2）。 – 2014-10-19 13:43:46

@SalvadorDali您可以將'Counter'看作您在解決方案中用字典所做的一個抽象，所以它仍然是O（N）:-) – thefourtheye 2014-10-19 13:44:37

如果順序並不重要：

>>> a = [1, 2, 3, 3, 3, 5, 8, 1, 8] 
>>> list(set([x for x in a if a.count(x)%2 == 1])) 
[2, 3, 5]

列表內涵[x for x in a if a.count(x)%2 == 1]收益僅出現在列表中的奇數次的元素。 list(set(...))是從列表中刪除重複條目的常用方法。

來源

2014-10-19 13:37:53

簡明但複雜度爲O（N ** 2）。 – 2014-10-19 13:45:39

是的，它肯定比其他答案效率低（我剛剛在上面的評論中注意到OP更喜歡'O（N）'解決方案）。 – 2014-10-19 13:47:26

你所能使用scipy.stats.itemfreq：

>>> from scipy.stats import itemfreq 
>>> xs = [1, 2, 3, 3, 3, 5, 8, 1, 8] 
>>> ifreq = itemfreq(xs) 
>>> ifreq 
array([[1, 2], 
     [2, 1], 
     [3, 3], 
     [5, 1], 
     [8, 2]]) 
>>> i = ifreq[:, 1] % 2 != 0 
>>> ifreq[i, 0] 
array([2, 3, 5])

來源

2014-10-19 13:46:22

從列表中刪除重複的元素，但只有那些有奇數重複的人

回答

相關問題