今日被问到一个所谓最简单的算法题，题目内容如下：
一个列表，数字连续，顺序无规律，从中剔除一个数，如何快速定位该数
最开始想到的方法是先排序，然后遍历列表，依次对前后元素做差，不等于1的元素+1，即为剔除的元素，于是具体实现为：
# method 2
def find_absence_2(lst):
lst = sorted(lst)
_len = len(lst) - 1
for i in range(_len):
if lst[i + 1] - lst[i] != 1:
return lst[i] + 1
后来知道答案后恍然大悟，才知道原来如此简单，其实用列表未剔除的和，减去剔除后的和，即得到目标值，是不是很简单？
# method 1
def find_absence(lst):
lst = sorted(lst)
lst_end = lst[-1]
normal_sum = 0
for i in range(1, lst_end + 1):
normal_sum += i
absence_sum = 0
for i in lst:
absence_sum += i
return normal_sum - absence_sum
但是，奇怪的是，从执行效率来看，遍历列表的方法居然比做差的方法更省时一点，具体如下：
- 计算时间实现
......
if __name__ == '__main__':
upper = 10000000
target = random.randint(1, upper - 1)
lst = [n for n in range(1, upper) if n != target]
start = time.time()
print(find_absence(lst) == target)
end = time.time()
print('run method 1 spend time is ', (end - start))
start = time.time()
print(find_absence_2(lst) == target)
end = time.time()
print('run method 2 spend time is ', (end - start))
......
- 运行结果如下
李迪@freedomLiDi MINGW64 /f/learnPython (master)
$ python find_absence_num.py
True
run method 1 spend time is 1.453
True
run method 2 spend time is 1.391
李迪@freedomLiDi MINGW64 /f/learnPython (master)
$ python find_absence_num.py
True
run method 1 spend time is 1.453
True
run method 2 spend time is 0.953
OK！
~
~
~
不积跬步，无以至千里
