欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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