使用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次
方法:
我们可以使用以下四个步骤有效地查找向量中元素的频率:
- 遍历给定向量 vec 。
- 检查当前元素是否存在于map中。
- 如果它存在,则更新当前元素的频率,否则将该元素插入其中,频率为1,如下所示:
- 遍历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)。