力扣 2080. 区间内查询数字的频率 离散化 二分 开区间 左闭右开区间 lowerBound

Problem: 2080. 区间内查询数字的频率

👨‍🏫 参考题解
👨‍🏫 参考视频

🍚 左闭右开二分

class RangeFreqQuery {
    private final Map<Integer, List<Integer>> pos = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
             //初始化时，存放每个元素出现的下标位置，这个list本身已经是有序的，因为我们是按照下标开始存进去的，存的也是下标
            pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> a = pos.get(value);
        if (a == null) {
            return 0;
        }
        return lowerBound(a, right + 1) - lowerBound(a, left);
    }

    // 开区间写法
    // 请看 https://www.bilibili.com/video/BV1AP41137w7/
    // 找到第一个 >= target 的下标，没有则返回数组长度
    private int lowerBound(List<Integer> a, int target) {
        // 左闭右开区间 [left, right)
        int left = 0;
        int right = a.size();
        while (left < right) { // 区间不为空
            int mid = (left + right) >>> 1;
            if (a.get(mid) < target) {
                left = mid + 1; // 范围缩小到 [mid + 1, right)
            } else {
                right = mid; // 范围缩小到 [left, mid)
            }
        }
        return left; // right 是最小的满足 a[right] >= target 的下标
    }
}

🍚 开区间二分

class RangeFreqQuery {
    private final Map<Integer, List<Integer>> pos = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
             //初始化时，存放每个元素出现的下标位置，这个list本身已经是有序的，因为我们是按照下标开始存进去的，存的也是下标
            pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> a = pos.get(value);
        if (a == null) {
            return 0;
        }
        return lowerBound(a, right + 1) - lowerBound(a, left);
    }

    // 开区间写法
    // 请看 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(List<Integer> a, int target) {
        // 开区间 (left, right)
        int left = -1;
        int right = a.size();
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // a[left] < target
            // a[right] >= target
            int mid = (left + right) >>> 1;
            if (a.get(mid) < target) {
                left = mid; // 范围缩小到 (mid, right)
            } else {
                right = mid; // 范围缩小到 (left, mid)
            }
        }
        return left; // right 是最小的满足 a[right] >= target 的下标
    }
}