C++程序区间查询数组元素频率

给定一个包含n个非负整数的数组。任务是在 数组的任意范围 内找到特定元素的频率。范围在数组中给出为位置（不是基于0的索引）。可能会有多个给定类型的查询。

例如：

输入: arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
left = 2, right = 8, element = 8
left = 2, right = 5, element = 6

输出: 3
1
元素8在arr [left-1..right-1]中出现了3次
元素6在arr [left-1..right-1]中出现了1次

Naive方法： 从左至右遍历并在找到元素时更新计数变量。

下面是Naive方法的代码：

//C++程序查找范围内元素的总计数
#include
using namespace std;
  
// 返回arr[left-1..right-1]中元素的计数
int findFrequency(int arr[], int n, int left,
                         int right, int element)
{
    int count = 0;
    for (int i=left-1; i<=right; ++i)
        if (arr[i] == element)
            ++count;
    return count;
}
  
// 驱动程序
int main()
{
    int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // 打印1到6位置的2的频率
    cout << "Frequency of 2 from 1 to 6 = "
         << findFrequency(arr, n, 1, 6, 2) << endl;
  
    // 打印4到9位置的8的频率
    cout << "Frequency of 8 from 4 to 9 = "
         << findFrequency(arr, n, 4, 9, 8);
  
    return 0;
}

输出：

 Frequency of 2 from 1 to 6 = 1
 Frequency of 8 from 4 to 9 = 2

时间复杂度 ：O(right-left+1) 或 O(n)

辅助空间 ：O(1)

一种 高效的方法 是使用哈希。在C++中，我们可以使用unordered_map。

首先，我们将每个不同元素的位置存储为一个向量，例如：

int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
map[2] = {1, 8}
map[8] = {2, 5, 7}
map[6] = {3, 6}
以此类推......

由于我们可以看到map[]中的元素已经按排序顺序排列（因为我们从左到右插入元素），因此答案归结为使用类似于二进制搜索的方法在hash map[]中找到总计数。
在C++中，我们可以使用lower_bound()返回指向范围[first,last]中第一个值不小于 ‘left’ 的元素的迭代器，而upper_bound()将返回指向范围[first，last)中第一个大于’right’的元素的迭代器。
之后我们只需要减去upper_bound()和lower_bound()的结果就可以得到最终的答案。例如，假设我们想要在范围[1到6]中查找数字8的总计数，那么lower_bound()函数中map[8]将返回结果0（指向2），而upper_bound()将返回2（指向7），因此我们需要减去两个结果，即2-0=2。以下是以上方法的代码：
“`cpp // C++程序：区间查询数组元素频率
#include
using namespace std;

// 返回arr[left-1..right-1]中元素的计数
int findFrequency(int arr[], int n, int left,
                         int right, int element)
{
    unordered_map > subsets;
    int ans = 0;
    for (int i = 0; i < n; i++)
        subsets[arr[i]].push_back(i);

    auto i = lower_bound(subsets[element].begin(),
                          subsets[element].end(),
                          left – 1);
    auto j = upper_bound(subsets[element].begin(),
                          subsets[element].end(),
                          right – 1);

    ans = j – i;
    return ans;
}

// 驱动程序
int main()
{
    int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 打印1到6位置的2的频率
    cout << "Frequency of 2 from 1 to 6 = "
         << findFrequency(arr, n, 1, 6, 2) << endl;

    // 打印4到9位置的8的频率
    cout << "Frequency of 8 from 4 to 9 = "
         << findFrequency(arr, n, 4, 9, 8);

    return 0;
}</li>
</ol>

<pre><code class=" line-numbers">“`cpp // C ++程序，用于查找元素的总计数
// C++ program to find total count of an element
#include<bits/stdc++.h>
using namespace std;

unordered_map< int, vector<int> > store;

// Returns frequency of element in arr[left-1..right-1]
int findFrequency(int arr[], int n, int left,
int right, int element)
{
// Find the position of first occurrence of element
int a = lower_bound(store[element].begin(),
store[element].end(),
left)
– store[element].begin();

// Find the position of last occurrence of element
int b = upper_bound(store[element].begin(),
store[element].end(),
right)
– store[element].begin();

return b-a;
}

// Driver code
int main()
{
int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
int n = sizeof(arr) / sizeof(arr[0]);

// Storing the indexes of an element in the map
for (int i=0; i<n; ++i)
store[arr[i]].push_back(i+1); //starting index from 1

// Print frequency of 2 from position 1 to 6
cout << “Frequency of 2 from 1 to 6 = ”
<< findFrequency(arr, n, 1, 6, 2) <<endl;

// Print frequency of 8 from position 4 to 9
cout << “Frequency of 8 from 4 to 9 = ”
<< findFrequency(arr, n, 4, 9, 8);

return 0;
}

输出：
```
Frequency of 2 from 1 to 6 = 1
Frequency of 8 from 4 to 9 = 2
```
如果我们有许多查询问一个任意范围的特定元素的总频率，那么这种方法将是有益的。

时间复杂度： 单个查询的O（log N）。