使用C++中的map查找向量中每个元素的频率的程序

使用C++中的map查找向量中每个元素的频率的程序

给定一个向量 vec ,任务是使用map查找 vec 中每个元素的频率。

例子:

输入:vec = {1, 2, 2, 3, 1, 4, 4, 5}

输出:

1 2

2 2

3 1

4 2

5 1

解释:

1出现了2次

2出现了2次

3出现了1次

4出现了2次

5出现了1次

输入:v1 = {6, 7, 8, 6, 4, 1}

输出:

1 1

4 1

6 2

7 1

8 1

解释:

1出现了1次

4出现了1次

6出现了2次

7出现了1次

8出现了1次

方法:

我们可以使用以下四个步骤有效地查找向量中元素的频率:

  1. 遍历给定向量 vec
  2. 检查当前元素是否存在于map中。
  3. 如果它存在,则更新当前元素的频率,否则将该元素插入其中,频率为1,如下所示:
  4. 遍历map并打印存储为映射值的每个元素的频率。

下面是上述方法的实现:

#include <bits/stdc++.h>
using namespace std;
 
void printFrequency(vector<int> vec)
{
    // 定义一个map
    map<int, int> M;
 
    // 遍历向量vec,检查当前元素是否存在
    // 如果没有找到当前元素,则插入
    // 当前元素,频率为1
    for (int i = 0; vec[i]; i++) {
 
        if (M.find(vec[i]) == M.end()) {
            M[vec[i]] = 1;
        }
 
        // 否则更新频率
        else {
            M[vec[i]]++;
        }
    }
 
    // 遍历map以打印频率
    for (auto& it : M) {
        cout << it.first << ' '
             << it.second << '\n';
    }
}
 
// 驱动程序
int main()
{
    vector<int> vec = { 1, 2, 2, 3, 1, 4, 4, 5 };
 
    // 调用函数
    printFrequency(vec);
    return 0;
}  

输出:

1 2
2 2
3 1
4 2
5 1

复杂度分析:

时间复杂度: O(n log n)

对于给定的大小为n的向量,我们遍历了它一次,查找map中的元素的时间复杂度为O(log n)。因此时间复杂度为O(n log n)。

空间复杂度: O(n)

对于给定大小为n的向量,我们使用了一个额外的map,它最多可以有n个键值对,因此空间复杂度为O(n)。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例