代理记账一个月多少钱一个月_网站维护员招聘_品牌建设的五个要素_站长工具seo优化

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] >= targetint mid = (left + right) >>> 1;if (a.get(mid) < target) {left = mid; // 范围缩小到 (mid, right)} else {right = mid; // 范围缩小到 (left, mid)}}return left; // right 是最小的满足 a[right] >= target 的下标}
}