20250218力扣每日一题

知识点

c++中vector的lower_bound和upper_bound操作：
- lower_bound
  - 传入的参数：查找范围初始点的迭代器，查找范围结束点的迭代器，待查找的目标值
  - 返回值：返回指向第一个大于等于目标值的元素的迭代器
  - 用法：auto l = lower_bound(pos.begin(), pos.end(), value)
- upper_bound
  - 传入的参数：查找范围初始点的迭代器，查找范围结束点的迭代器，待查找的目标值
  - 返回值：返回指向第一个大于目标值的元素的迭代器
  - 用法：auto r = upper_bound(pos.begin(), pos.end(), value)
- 如果没有查找到目标值，那么两个操作返回的内容均为pos.end()

解题思路

每次查询的过程分为两步
1. 得到目标数value在数组arr中的所有下标
2. 在这些下标中计算位于闭区间的[left, right]的下标个数并返回
由于arr初始化后就不在变化，可以构建以arr中元素值为键，值的对应下标数组为值的哈希表，来存储数组中的信息
构建哈希表时，我们顺序遍历arr数组，这样保证了每个键对应的下标数组都是有序的
查找时，根据传入的参数中的value找到对应的下标数组
- 首先查找第一个大于等于left的下标的迭代器l位置
- 其次查找第一个大于right的下标的迭代器r位置
返回r - l，即为答案

实现代码

题解代码

class RangeFreqQuery {
private:
    unordered_map<int, vector<int>> occurence;
public:
    RangeFreqQuery(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0; i < n; i ++)
            occurence[arr[i]].push_back(i);
    }

    int query(int left, int right, int value) {
        const vector<int> &pos = occurence[value];

        auto l = lower_bound(pos.begin(), pos.end(), left);
        auto r = upper_bound(pos.begin(), pos.end(), right);

        return r - l;

    }
};

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

我的代码（超时了，无敌了，炸了）

class RangeFreqQuery {
private:

    vector<int> nums;

public:
    RangeFreqQuery(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0; i < n; i ++){
            nums.push_back(arr[i]);
        }

    }

    int query(int left, int right, int value) {
        vector<int> subnums(nums.begin() + left, nums.begin() + right);
        sort(subnums.begin(), subnums.end());
        int l = 0, r = subnums.size() - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(subnums[mid] >= value)
                r = mid;
            else
                l = mid + 1;
        }
        int index_1 = l;

        l = 0, r = subnums.size() - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(subnums[mid] <= value){
                l = mid;
            }else
                r = mid - 1;
        }
        int index_2 = l;

        return index_2 - index_1 + 1;
    }
};

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

知识点

解题思路

实现代码

题解代码

我的代码（超时了，无敌了，炸了）

Enjoy Reading This Article?