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

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。

  1. 首先,我们将每个不同元素的位置存储为一个向量,例如:
int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
map[2] = {1, 8}
map[8] = {2, 5, 7}
map[6] = {3, 6}
以此类推......
  1. 由于我们可以看到map[]中的元素已经按排序顺序排列(因为我们从左到右插入元素),因此答案归结为使用类似于二进制搜索的方法在hash map[]中找到总计数。
  2. 在C++中,我们可以使用lower_bound()返回指向范围[first,last]中第一个值不小于 ‘left’ 的元素的迭代器,而upper_bound()将返回指向范围[first,last)中第一个大于’right’的元素的迭代器。
  3. 之后我们只需要减去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)。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例