bisect 庫
本來是想自己實現但是複雜度太高,偶然搜到 python 中有一個庫 bisect 可以實現真的是太妙了 。
bisect
基本用法,使用起來很方便,其實就是在找可以插入的位置,但是不會真的插入:
import bisect
l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
bisect.bisect(l, 55) # returns 7
耗時測試,從結果來看 bisect 的速度最快:
import timeit
import bisect
print(timeit.timeit('bisect.bisect([1, 4, 9, 16, 25, 36, 49, 64, 81, 100], 55)','import bisect'))
# 0.2991909169941209
print(timeit.timeit('next(i for i,n in enumerate([1, 4, 9, 16, 25, 36, 49, 64, 81, 100]) if n > 55)'))
# 0.7511563330190256
print(timeit.timeit('next(([1, 4, 9, 16, 25, 36, 49, 64, 81, 100].index(n) for n in [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] if n > 55))'))
# 0.6965440830099396
bisect_left 和 bisect_right
另外還有兩種常用方法,bisect_left 和 bisect_right 函式,用入處理將會插入重複數值的情況,返回將會插入的位置。
- bisect_left(seq, x) x 存在時返回 x 左側的位置
- bisect_right(seq, x) x 存在時返回 x 右側的位置
舉例:
print(bisect.bisect_left([2,4,7,9],2))
# 0
print(bisect.bisect_left([2,4,7,9],3))
# 1
print(bisect.bisect_right([2,4,7,9],2))
# 1
print(bisect.bisect_right([2,4,7,9],3))
# 1
insort
把目標值插入到有序序列中,並能保持有序順序
arr=[2,4,7,9]
bisect.insort(arr,6)
arr # [2, 4, 6, 7, 9]
「其他文章」
- leetcode 2258. Escape the Spreading Fire(python)
- leetcode 2257. Count Unguarded Cells in the Grid(python)
- leetcode 2273. Find Resultant Array After Removing Anagrams(python)
- leetcode 1209. Remove All Adjacent Duplicates in String II(python)
- leetcode 1396. Design Underground System (python)
- leetcode 1679. Max Number of K-Sum Pairs (python)
- leetcode 216. Combination Sum III(python)
- 解決安裝 CUDA 10.0 報錯未安裝元件
- 解決安裝 anaconda 時報錯 failed to create menus
- anaconda 建立虛擬環境時報錯 HTTP errors 解決辦法
- 解決 could not load dynamic library cudart64_100.dll
- leetcode 2244. Minimum Rounds to Complete All Tasks(python)
- leetcode 2245. Maximum Trailing Zeros in a Cornered Path (python)
- leetcode 2241. Design an ATM Machine(python)
- leetcode 2240. Number of Ways to Buy Pens and Pencils (python)
- leetcode 2239. Find Closest Number to Zero (python)
- tensorflow 1.x 實戰教程(十一)—模型的儲存與恢復
- tensorflow 1.x 實戰教程(十)—迴圈神經網路
- tensorflow 1.x 實戰教程(八)—學習率衰減並在 TensorBoard 中顯示變數變化
- tensorflow 1.x 實戰教程(七)——加入 Dropout 的分類模型