[LeetCode] 2080. Range Frequency Queries

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:
RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left…right].
A subarray is a contiguous sequence of elements within an array. arr[left…right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:
Input
[“RangeFreqQuery”, “query”, “query”]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output
[null, 1, 2]

Explanation
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4]
rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

Constraints:
1 <= arr.length <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
At most 105 calls will be made to query

区间内查询数字的频率。

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

思路

首先我解释一下题意，尤其是 query 的部分。题目给的是一个数组，比如这样的
[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]
然后题目让我们求的是在某一个区间[left, right]内，一个目标值的出现次数。比如query(1, 2, 4)，就是求[33, 4]这个区间内4的出现次数；query(0, 11, 33)，就是求[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]这个区间内33的出现次数。

对于一个数字在 input 数组内出现的下标，我们可以用一个 hashmap 存起来。至于如何高效地找到在某个区间 [left, right] 内到底有几个数字，则需要用到二分法。

注意代码内二分的 helper 函数 helper(left, right, target) 的含义是找在区间 [left, right] 内（实际是在某个数字对应的所有下标）第一个 >= target 的数字的下标。因为我们找的是在一段区间[left, right]内的目标值，所以我们可以找

• 目标值 target 出现且大于 left 的位置
• 目标值 target 出现且大于 right 的位置

如果目标值 target 出现的位置直接小于 left 或者 直接就大于 right 了，则说明 target 不在区间 [left, right] 内。

复杂度

时间O(n) + O(logn) = O(n)
空间O(n)

代码

Java实现

class RangeFreqQuery {
	HashMap<Integer, List<Integer>> map;

    public RangeFreqQuery(int[] arr) {
        map = new HashMap<>();
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int num = arr[i];
			if (!map.containsKey(num)) {
				map.put(num, new ArrayList<>());
			}
			map.get(num).add(i);
		}
    }
    
    public int query(int left, int right, int value) {
        List<Integer> list = map.get(value);
		if (list == null) {
			return 0;
		}
		// 找list中第一个 >= left 的下标
		int first = helper(list, 0, list.size() - 1, left);
		if (list.get(first) > right || list.get(first) < left) {
			return 0;
		}
		// 找list中第一个 >= right 的下标
		int second = helper(list, 0, list.size() - 1, right);
		if (list.get(second) > right) {
			second--;
		}
		return second - first + 1;
    }

	private int helper(List<Integer> list, int left, int right, int target) {
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (list.get(mid) < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		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);
 */