LeetCode 2080 Range Frequency Queries

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 <= 10<sup>5</sup>
• 1 <= arr[i], value <= 10<sup>4</sup>
• 0 <= left <= right < arr.length
• At most 10<sup>5</sup> calls will be made to query

题目大意：

设计数据结构，支持在指定的子数组中某target的频数。

解题思路：

这题有意思，有望成为经典题。第一种方法写用以每个字母为结尾的frequency_dict作为数据结构，query只需要用frequency_dict[right]-frequency_dict[left-1]，
空间复杂度为O(n2)得到TLE。第二种方法用bucket sort，就是将值作为key存到dict中，而value是下标List，query时候得到对应List，遍历
一次即可，但仍然得到TLE。第三种方法改进用Binary search得到下标List的左右界。二分法用greater_or_equal_position以及small_or_equal_position.
所以最终方案采取bucket sort + binary search

解题步骤：

1. dict记录值到下标列表的映射
2. 二分法找left和right的index从而求个数

注意事项：

1. Binary search用greater_or_equal_position以及small_or_equal_position.

Python代码：

class RangeFreqQuery:
	
    def __init__(self, arr: List[int]):
        self.frequency_dict = {}

        for i, n in enumerate(arr):
            if n not in self.frequency_dict:
                self.frequency_dict[n] = [i]
            else:
                self.frequency_dict[n].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.frequency_dict:
            return 0
        index_list = self.frequency_dict[value]
        '''
        count = 0
        for index in index_list:
            if left <= index <= right:
                count += 1
        '''
        left_pos = self.greater_or_equal_position(index_list, left)
        right_pos = self.smaller_or_equal_position(index_list, right)
        if left_pos == -1 or right_pos == -1:
            return 0
        return right_pos - left_pos + 1

    def greater_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                start = mid
        if nums[start] >= target:
            return start
        if nums[end] >= target:
            return end
        return -1

    def smaller_or_equal_position(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) // 2
            if target > nums[mid]:
                start = mid
            elif target < nums[mid]:
                end = mid
            else:
                end = mid
        if nums[end] <= target:
            return end
        if nums[start] <= target:
            return start
        return -1

用defaultdict(list)和bisect来优化程序

Python代码：

def __init__(self, arr: List[int]):
	self.frequency_dict = collections.defaultdict(list)

	for i, n in enumerate(arr):
		self.frequency_dict[n].append(i)

def query(self, left: int, right: int, value: int) -> int:
	index_list = self.frequency_dict[value]
	left_pos = bisect.bisect(index_list, left - 1)
	right_pos = bisect.bisect(index_list, right)
	return right_pos - left_pos

算法分析：

时间复杂度为O(logn)，空间复杂度O(n)。