第78天：100天DSA编程挑战

Source: Dev.to

简介

接受一个新挑战：每天解答 GeeksforGeeks POTD 并分享我的解法！💻🔥
目标：提升问题解决能力，提升编码水平，并且每天学习新东西。关注我的旅程！🚀

#100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

问题描述

给定一个已排序的数组 arr[] 和一个二维数组 queries[][]，其中 queries[i] 表示形如 [l, r, x] 的查询。
对于每个查询，统计数字 x 在子数组 arr[l...r] 中出现的次数（source）。

示例

示例 1

输入

arr[] = [1, 2, 2, 4, 5, 5, 5, 8]
queries[][] = [[0, 7, 5], [1, 2, 2], [0, 3, 7]]

输出

[3, 2, 0]

解释

• 查询 [0, 7, 5] → 子数组 [1, 2, 2, 4, 5, 5, 5, 8]；5 出现了 3 次。
• 查询 [1, 2, 2] → 子数组 [2, 2]；2 出现了 2 次。
• 查询 [0, 3, 7] → 子数组 [1, 2, 2, 4]；7 未出现。

示例 2

输入

arr[] = [1, 3, 3, 3, 6, 7, 8]
queries[][] = [[0, 3, 3], [4, 6, 3], [1, 5, 6]]

输出

[3, 0, 1]

解释

• 查询 [0, 3, 3] → 子数组 [1, 3, 3, 3]；3 出现了 3 次。
• 查询 [4, 6, 3] → 子数组 [6, 7, 8]；3 未出现。
• 查询 [1, 5, 6] → 子数组 [3, 3, 3, 6, 7]；6 出现了 1 次。

约束条件

• 1 ≤ arr.size(), queries.size() ≤ 10⁵
• 1 ≤ arr[i], x ≤ 10⁶
• 0 ≤ l ≤ r < arr.size()

解法

from bisect import bisect_left, bisect_right

class Solution:
    def countXInRange(self, arr, queries):
        """
        Returns a list where each element corresponds to the count of x in the
        subarray arr[l...r] for each query [l, r, x].
        """
        res = []
        for l, r, x in queries:
            left = bisect_left(arr, x, l, r + 1)
            right = bisect_right(arr, x, l, r + 1)
            res.append(right - left)
        return res