突然之间觉得不知道写些什么内容好（虽然我之前积累了不少的课外书的读书笔记/记录，但不是和代码/安全相关的内容感觉也不太好直接将发文章将书的目录等内容放在blog上{如果个人想法较多、较为私人性质的话干脆设置个密码or直接置位私密，个自己看就行}，总觉得文章如果能有些代码在里面，然后具备一定的启发性质，记录在面对问题时的思考过程、解决方法的转变等内容会更有启发性），然后浏览到了一篇讲面试题的文章，自己没有直接看解决方案，先思考了一会，然后和作者的思路、答案进行了比较，觉得很享受这个过程（而且这种内容对以后可能的面试也会有一定帮助的），所以决定以后在暂时没有其它内容想写的时候写一些比较好玩的面试题，做做脑力体操。下面就是第一道题目：

题目：有一个长度是101的数组，存有1 ~ 100这100个数字，其中有一个是重复的。请设计一个算法找出这个重复的数字。

我想了一阵之后觉得方法的话貌似可以采用Python的set结构去重，然后用原有list减去去重之后的list来搞定（没有写代码，只是考虑的可行的思路/方案，但后来搜索了之后才知道Python的list不支持减法，只有set可以做减法，又因为这里的两个set是相同的，思路就卡在这里了），不过后来还是用另一种方法解决了，思路的话参见：去重的各种方法[不定期更新]。

然后再去看作者的思路：先排序，然后顺序查找值相同的元素即是唯一重复的数字。

再看文章下面的评论，还有一个更具针对性，同时也更快的方法：直接把这101个数字加起来，然后减去5050，就是那个重复的数字。比如1，2，2，3，这4个数字，加起来是8，然后减去1+2+3，最后结果是2，那么2就是重复的（因为题目已经限定得很清楚了，考的就是读题能力）。

其余的方法如下：

1.利用sort和uniq进行处理

$ cat t
5,2,1,9,6,2,8
$ cut -d',' --output-delimiter=' ' -f1- <t | tr ' ' 'n' | sort | uniq -c | awk '!/ 1 / {print $2}'
2

上面这个也是先利用sort排序，然后用uniq的-c选项计算出各个元素出现次数，最后用awk打印不是1的那个即可得到结果。

2.利用collections模块

>>> arr1 = [5,2,1,9,6,2,8]
>>> import collections
>>> collections.Counter(arr1).most_common(1)[0][0]
2

3.利用列表自带的count()函数

>>> arr1 = [5,2,1,9,6,2,8]
>>> [i for i in arr1 if arr1.count(i) == 2]
[2, 2]

4.原作者的方法

#!/usr/bin/env python
#-*- coding:utf-8 -*-
arr1 = [5,2,1,9,6,2,8]

arr2 = {}.fromkeys(arr1).keys()
print arr2    #效率高，但不符合题目要求

arr3 = list(set(arr1))
print arr3    #效率更高，但仍然不符合题目要求

arr4 = sorted(arr1)
i = len(arr4) - 1
for x in range(i):
    y = x + 1
    if arr4[x] == arr4[y]:
        print arr4[x]    #达到题目要求了

5.我的解决方法

arr1 = [5,2,1,9,6,2,8]
dic = {}
i = len(arr1)
for x in range(i):
    if dic.get(arr1[x]) and dic[arr1[x]] == 1:
        print arr1[x]
    else:
        dic[arr1[x]] = 1

6.刚刚发现的另外一个解决方法

#刚刚发现的另外一个简洁的方案（只打印出现一次的元素组成的列表）
>>> s=[11,22,11,44,22]
>>> [(s[i]) for i in range(len(s)) if s.count(s[i])<2]
[44]	#只出现1次的元素组成的新list
>>> [(s[i],i) for i in range(len(s)) if s.count(s[i])<2]
[(44, 3)]	#只出现1次的元素及其对应的下标位置

如果是题目中的要求的话就是：

>>> arr5=[arr1[i] for i in range(len(arr1)) if arr1.count(arr1[i])>1]
[2, 2]
>>> print list(set(arr5))
[2]

---

在实际写该方法的过程中碰到的一些问题（主要是因为对Python的list、dict的结构不熟悉以及实际遇到的情况较少导致的）记录如下：

1.KeyError错误

>>> arr1 = [5,2,1,9,6,2,8]
>>> dic = {}
>>> i = len(arr1) - 1
>>> for x in range(i):
...     if dic[arr1[x]] != 1:
...         dic[arr1[x]] = 1
...     else:
...         print arr1[x]
...
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
KeyError: 5

去网上搜索问题原因：

Python中dict报KeyError的问题

如果不知道dict中是否有key的值，那么最好用 dict.get(key) 方法；如果用dict[key]这个方法读取不存在的元素就会报KeyError异常（所以需要根据不同情况用不同的方式）
dict.get方法主要是提供一个取不到对应key的value就返回默认值的功能，而dict[key]实际上是调用了__getitem__方法，你也可以重写这个方法。

2.Python的list的减法操作

两个 list 相减
就是比如：
a=[1,2,3,4,5]
b=[2,3,4]
a-b需要得到[1,5]

但是 Python list 不支持减法，所以只能使用Python的set结构投机取巧了~呵呵
我们来用set()如下：
print list (set(a)-set(b))
[1,5] #结果

3.如何找出Python的list中重复的项

>>> s=[11,22,11,44,22]
>>> [(s[i],i) for i in range(len(s)) if s.count(s[i])>1]
[(11, 0), (22, 1), (11, 2), (22, 4)]

用defaultdict来试试：

from collections import defaultdict
s=[11,22,11,44,22,33]
d = defaultdict(list)
for k,va in [(v,i) for i,v in enumerate(s)]:
    d[k].append(va)
d.items()

还有：

>>> from collections import Counter
>>> Counter([11,22,11,44,22,33])
Counter({11: 2, 22: 2, 33: 1, 44: 1})

 

参考地址：

• Python列表[list]去重
• 去重的各种方法[不定期更新]
• 如何找出 python list 中有重复的项
• python中list类型相减
• python 中对list做减法操作