一道Python面试题

看到Hey!Linux张贴出的一道面试题

我感觉性能多耗在排序和列表内元素两两比较上,我想了另一种思路：源列表生成一个集合，源列表和新集合各项元素总和的差就是重复的那个数，代码如下:

#!/usr/bin/env python3
arr1 = [i for i in range(1,1000000)]+[500000]  
arr4 = set(arr1)  
print(sum(arr1)-sum(arr4))  

代码略简洁，那性能是不是也会更好呢？为了明显比较两种算法性能,我将列表范围扩大到1～1000000,并将重复值设在中位数500000,将他的算法重写如下:

#!/usr/bin/env python3
arr1 = [i for i in range(1,1000000)]+[500000]  
arr4 = sorted(arr1)  
i = len(arr4) - 1  
for x in range(i):  
    y = x + 1
    if arr4[x] == arr4[y]:
        print(arr4[x])

分别测试，结果分别为0.53s和0.70s,我的算总和再相减的方法略快点，不过也不一定，看情况:
当重复值在出现在列表前几个元素，则列表内两两元素比较算法快，因为只需比较前几个元素就结束;但当重复值越往后，列表内两两元素比较的方法相应就更慢了～