bisect_left和bisect_right的区别

发表于 分类于 阅读次数：

老是忘记这两的区别，特此记录。

参考链接

bisect_left(a, x)

返回数组a中第一个大于等于x的下标i，如果不存在（x比a中最大的数都大）那么返回len(a)

可以用来判断数组a中大于等于x的数是否存在

1
2
3
4
5
i = bisect_left(a, x)
if i != len(a):
	数组a中存在数比x大或者等于x
else:
	不存在

bisect_right(a, x)

返回数组a中第一个大于x的下标，如果不存在返回len(a）

比如 a = [1,2,2,2,3]

bisect_left(a, 2) 返回 1

bisect_right(a, 2) 返回 4

例题

220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

  • i != j,
  • abs(i - j) <= indexDiff
  • abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true ；否则，返回 false 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from sortedcontainers import SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        arr = SortedList()
        for i in range(len(nums)):
            if i > indexDiff:
                arr.remove(nums[i-indexDiff-1])
            # arr 中存在 x
            # nums[i]-valueDiff <= x <= nums[i]+valueDiff
            j = bisect_left(arr, nums[i]-valueDiff)
            if j != len(arr) and arr[j] <= nums[i] + valueDiff:
                return True
            arr.add(nums[i])
        return False