第18天(中等题 二分查找)

打卡第十八天
2道中等题

题目:

思路: 存下标将大的arr找二分变成 目标值对应下标arr的位置，最后r-l这个小二分

代码:

class RangeFreqQuery {unordered_map<int, vector<int>> pos;//哈希表public:RangeFreqQuery(vector<int>& arr) {for (int i = 0; i < arr.size(); i++) {//遍历数组pos[arr[i]].push_back(i);//pos[arr[i]]：获取数值 arr[i] 对应的位置列表//.push_back(i)：将当前索引 i 添加到该数值的位置列表中}}int query(int left, int right, int value) {auto it = pos.find(value);//查找value是否在列表里if (it == pos.end()) {return 0;}auto& a = it->second;//把下标列表记作数组areturn ranges::upper_bound(a, right) - ranges::lower_bound(a, left);//返回left ≤ i ≤ right 的下标i的个数}
};

通用的lowerBound用法总结

耗时≈一小时 明天继续