一道面试题

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

 #!/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) - 1for x in range(i):    y = x + 1    if arr4[x] == arr4[y]:        print arr4[x]#达到题目要求了，可惜面试时间已过#当时怎么就没有想到用sorted这个方法呢#还是自己技术太差了#惭愧啊惭愧

有哪位前辈有效率更高的算法，还请告诉我这个菜鸟，谢谢。