leetcode day 14【5186. 区间内查询数字的频率】第一次周赛

• 第一次用暴力—>超时
• 第二次在初始化时用字典存每个数字出现的位置但查询时还是顺序查找---->超时
• 第三次用字典+二分查找---->AC
  特别要注意这里定位left和right时有轻微差别，left返回的索引应该是不小于它的第一个值的索引（右边），right返回的是大于它的第一个值的索引的前一位（左边）。所以在编写binary_find时要用一个bool值区分左右两种情况。

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.countdict = defaultdict(list)
        for idx, ele in enumerate(arr):
            self.countdict[ele].append(idx)

    def binary_find(self, arr: List[int], value, L: int, R: int, LEFT: bool) -> int:
        while L <= R:
            m = (L + R) // 2
            if arr[m] < value:
                L = m + 1
            elif arr[m] > value:
                R = m -1                
            else:
                return m
        return L if LEFT else R

    def query(self, left: int, right: int, value: int) -> int:
        count = 0
        if value not in self.countdict or left > self.countdict[value][-1] or right < self.countdict[value][0]:
            return 0
        leftidx = self.binary_find(self.countdict[value], left, 0, len(self.countdict[value])-1, True)
        rightidx = self.binary_find(self.countdict[value], right, leftidx, len(self.countdict[value])-1, False)
        return rightidx-leftidx+1

• 后来看了下其他人的解法，貌似可以直接用bisect模块：

bisect.bisect_left(arr, value)返回的是不小于value的第一个索引，
bisect.bisect_right(arr, value)返回的是不大于value的最后一个索引+1，

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.countdict = defaultdict(list)
        for idx, ele in enumerate(arr):
            self.countdict[ele].append(idx)

    def query(self, left: int, right: int, value: int) -> int:
        count = 0
        if value not in self.countdict or left > self.countdict[value][-1] or right < self.countdict[value][0]:
            return 0
        leftidx = bisect.bisect_left(self.countdict[value], left)
        rightidx = bisect.bisect_right(self.countdict[value], right)
        return rightidx - leftidx

1. 小技巧：可以用defaultdict来初始化列表字典：dict = defaultdict(list)，这样就不用判断每次字典中不存在键的时候初始化列表了，可以直接append。
2. 对于在有序列表中查找要插入的新元素的位置（插排），可以直接调用python的bisect模块获得索引值，其内部是基于二分实现。