【算法题】输出只出现一次的数字

问题

有一个全是数字的列表，其中有一个数字只出现一次，其他数字全部出现两次，输出只出现一次的数字

解法一

首先我们很容易知道这个数字列表的长度为奇数，可以先对列表进行排序。这样出现两次的数字就是排在一起的。然后我们对除了最后一个以外的数字按顺序两两比较，如果发现不相同，那么前面这个数字就是只出现一次的数字。如果全都相同，那么最后一个数字就是只出现一次的数字，算法如下：

def print_once(li):
    new_li = sorted(li)
    middle = len(new_li) >> 1
    for i in range(middle):
        if new_li[i*2] != new_li[i*2+1]:
            return new_li[i*2]
    return new_li[-1]    

解法二

collections库中有个 Counter 函数，可以以字典的形式统计出每个元素出现的次数，我们再通过 most_common 这个方法可以得到出现次数由大到小的排序，这样出现在最后一个的就是只出现一次的数字：

from collections import Counter

def print_once(li):
    return Counter(li).most_common()[-1][0]

解法三

我们可以将数字逐个加入到一个空集合中，在加入之前判断，如果集合中已经存在该元素，则将该元素删除，这样最后剩下的就是只出现一次的数字：

def print_once(li):
    s = set([])
    for i in li:
        if i in s:
            s.remove(i)
        else:
            s.add(i)
    return s.pop()