Leetcode--Java--5186(周赛T3)区间内查询数字的频率

Leetcode--Java--5186(周赛T3)区间内查询数字的频率 题目描述

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类：
RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
int query(int left, int right, int value) 返回子数组 arr[left…right] 中 value 的 频率 。
一个 子数组 指的是数组中一段连续的元素。arr[left…right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

样例描述

示例 1：

输入：
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]

解释：
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

思路

二分 + 哈希
本题核心思路是要建立每个值与其出现的所有下标集合的一个映射关系

1. 用哈希表建立映射，然后对于给定的值得到其下标集合。
2. 由于存储下标的集合是有序的，所以可以用二分，二分出最左下标和最右下标的位置，即可求得长度。二分出左右下标位置时记得判断是否越界，对于右边只判断是否大于right，大于的话就减一即可。
3. 注意二分判断条件的写法，第一个二分目标是找大于等于left的第一个位置，第二个二分目标是找小于等于right的第一个位置。各自的判断条件就是基于两个二分的目标！

代码

class RangeFreqQuery {
    Map> map;
    public RangeFreqQuery(int[] arr) {
       map = new HashMap<>();
       int n = arr.length;
       //建立每个值与其所有出现下标集合的映射
       for (int i = 0; i < n; i ++ ) {
           map.put(arr[i], new ArrayList<>());
       }
       for (int i = 0; i < n; i ++ ) {
           List indice = map.get(arr[i]);
           indice.add(i);
       }
    } 
    
    public int query(int left, int right, int value) {
          List indice = map.get(value);
          //不存在这个数
          if (indice == null) {
              return 0;
          }
          int l = 0, r = indice.size() - 1;
          //先二分出左侧端点
          while (l < r) {
              int mid = l + r >> 1;
              //找大于等于left的第一个位置
              if (indice.get(mid) >= left) {
                  r = mid;
              }else l = mid + 1;
          }
          int a = l;
          //判断是否在范围内
          if (indice.get(a) < left || indice.get(a) > right) return 0;
          //再二分右侧端点
         l = a;
         r = indice.size() - 1;
         while (l < r) {
             int mid = l + r + 1 >> 1;
             //找小于等于right的第一个位置
             if (indice.get(mid) <= right) {
                 l = mid;
             }
             else r = mid - 1;
         }
         int b = l;
         //防右端点越界，可写可不写
        //  if (indice.get(b) > right) {
        //      b --;
        //  } 
         return b - a + 1;
    }
}