文章目录

• 题目
• • 1、题目描述
  • 2、原题链接
• 解题报告
• • 1、解题思路
  • 2、解题方法
  • 2、代码详解
• 总结

题目

1、题目描述

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 $RangeFreqQuery$ 类：
  $RangeFreqQuery(int[]arr)$ 用下标从 $0$ 开始的整数数组 $arr$ 构造一个类的实例。
  $intquery(intleft,intright,intvalue)$ 返回子数组 $arr[left...right]$ 中 $value$ 的 频率 。
一个子数组指的是数组中一段连续的元素。$arr[left...right]$ 指的是 $nums$ 中包含下标 $left$ 和 $right$ 在内 的中间一段连续元素。
输入：
  [“RangeFreqQuery”, “query”, “query”]
  [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
  [null, 1, 2]

2、原题链接

区间内查询数字的频率

解题报告

1、解题思路

  （1）这题的暴力解法是每次查找的时候循环枚举对应范围内的数组找到 $value$ 出现的频率。这题的 $query$ 调用次数最多 1 0 5 10^5 105 次，肯定会超时。
  （2）使用哈希表把相同的值对应的数组下标存起来，在查询的时候只需要找对应哈希的数组就可。哈希数据 $hash<int,vector<int>>$
  （3）查找哈希表时，使用二分查找缩短查找时间。
  （4）找到 $l\ge r$ ，$l$ 为大于等于 $left$ 的值 $r$ 为小于等于 $right$ 的值。
  （5）返回 $r-l$

class RangeFreqQuery {private:     // 数值为键，出现下标数组为值的哈希表    unordered_map<int, vector> hash;    public:    RangeFreqQuery(vector& arr) { int n = arr.size(); for (int i = 0; i < n; ++i){     hash[arr[i]].push_back(i); }    } int query(int left, int right, int value) { // 查找对应的出现下标数组，不存在则为空 const vector& pos = hash[value]; // 两次二分查找计算子数组内出现次数 auto l = lower_bound(pos.begin(), pos.end(), left); auto r = upper_bound(pos.begin(), pos.end(), right); return r - l;    }};