2080 区间内查询数字的频率

题目描述#

给定一个整数数组 arr，需要支持以下操作：

public int query(int left,int right,int value)

返回在区间 [left, right] 中，元素值等于 value 的个数。

同时需要多次查询，要求高效。

示例：

arr = [1,3,1,2,3]
query(0, 4, 1) -> 2
query(1, 3, 3) -> 1
query(0, 2, 2) -> 0

思路#

用一个 Map<Integer, List<Integer>> 存储每个数值出现的位置索引：

键：元素值
值：该元素在数组中出现的所有下标（升序）

例如：

arr = [1,3,1,2,3]
map = {
  1 -> [0, 2],
  2 -> [3],
  3 -> [1, 4]
}

在查询时，只需在 map[value] 这个有序列表中，找到：

第一个 ≥ left 的下标位置
第一个 ≥ right + 1 的下标位置
两者之差就是区间中 value 出现的次数。

查找位置使用 二分查找，时间复杂度 O(log k)，其中 k 是该值出现的次数。

代码#

class RangeFreqQuery {
    Map<Integer, List<Integer>> map = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            map.putIfAbsent(arr[i], new ArrayList<>());
            map.get(arr[i]).add(i);
        }
    }

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

    public int lowwer(List<Integer> list, int target) {
        int left = 0;
        int right = list.size() - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (list.get(mid) >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery obj = new RangeFreqQuery(arr);
 * int param_1 = obj.query(left,right,value);
 */

知识边界#

map.putIfAbsent(arr[i], new ArrayList<>());#

putIfAbsent(K key, V value) 的语义是：

如果 Map 中 还没有这个 key，就执行 put(key, value)；如果已经存在，就什么都不做。

因此，它等价于：

if (!map.containsKey(key)) {
    map.put(key, value);
}

但更简洁、线程安全（在并发 Map 中尤为重要）。

map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);#

这行可以拆成两步理解：

map.computeIfAbsent(key, mappingFunction)
- 如果 key 不存在，就执行 mappingFunction.apply(key)，生成一个新值并放入 Map；
- 如果 key 已存在，则直接返回原来的值；
- 最后，返回这个 key 对应的 value。
.add(i)
- 因为返回的是一个 List<Integer>，所以可以直接在同一行调用 add(i)。