今日被問(wèn)到一個(gè)所謂最簡(jiǎn)單的算法題，題目?jī)?nèi)容如下：
一個(gè)列表泣洞，數(shù)字連續(xù)，順序無(wú)規(guī)律默色，從中剔除一個(gè)數(shù)球凰，如何快速定位該數(shù)
最開(kāi)始想到的方法是先排序，然后遍歷列表腿宰，依次對(duì)前后元素做差呕诉，不等于1的元素+1，即為剔除的元素吃度，于是具體實(shí)現(xiàn)為：
# 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
后來(lái)知道答案后恍然大悟甩挫，才知道原來(lái)如此簡(jiǎn)單，其實(shí)用列表未剔除的和椿每，減去剔除后的和伊者，即得到目標(biāo)值英遭，是不是很簡(jiǎn)單？
# 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
但是亦渗，奇怪的是挖诸，從執(zhí)行效率來(lái)看，遍歷列表的方法居然比做差的方法更省時(shí)一點(diǎn)法精，具體如下：
- 計(jì)算時(shí)間實(shí)現(xiàn)
......
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))
......
- 運(yùn)行結(jié)果如下
李迪@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多律！
~
~
~
不積跬步，無(wú)以至千里
