Python 中bisect用法说明
程序员文章站
2024-03-19 21:31:28
...
Python 中bisect用法说明
bisect是python内置模块,用于有序序列的插入和查找。
- 查找:
- bisect(array, item)
- bisect_left(array, item)
- bisect_right(array, item)
- 插入:
- insort(array,item)
- insort_left(array,item)
- insort_right(array,item)
1.查找
import bisect
arr = [1,3,3,6,8,12,15]
value = 3
idx_left=bisect.bisect_left(arr,value)
print(idx_left)
idx_right=bisect.bisect_right(arr,value)
print(idx_right)
# 用可变序列内置的insert方法插入
arr.insert(idx_left,value)
print(arr)
输出:
1
3
1,3,3,3,6,8,12,15
**NOTE:**left和不带left的用法的区别是:当插入的元素和序列中的某一个元素相同时,该插入到该元素的前面(左边,left),还是后面(右边);如果是查找,则返回该元素的位置还是该元素之后的位置。
2.插入
使用bisect.insort,比bisect先查找该插入哪个位置,再用insert方法插入更加快速的方法
import bisect
a = [1,4,6,8,12,15,20]
bisect.insort(a,13)
print(a)
[1,4,6,8,12,13,15,20]
3.使用举例
Leetcode-315题一种解决方案
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
n=len(nums)
result=[0]*n
sorted_nums=[]
for i in range(n-1,-1,-1):
idx = bisect.bisect_left(sorted_nums,nums[i])
sorted_nums.insert(idx,nums[i])
result[i] = idx
return result
上一篇: 网易笔试题:丰收(python解答,bisect)
下一篇: raft理论与实践[4]-lab2b