我有一系列的数字。,我需要找出哪些数字是重复的,并计算重复次数,。
我正在考虑通过两个数组来完成这个任务:
在第一种情况下,我将写数字,在第二种情况下,我将写出元素的重复次数。但要做到这一点,每个数字都必须不断地与第一个数字数组进行比较。
你对如何做一个更快的算法有什么想法吗?
示例:
数字数组:
1 9 7 8 9 6 9 8 7 1
结果将产生两个数组(如果您知道如何使用一个数组,那么就很酷了):
1个数组:
1 9 7 8 6
2个数组:
2 3 2 2 1
发布于 2022-05-01 06:26:28
在更糟糕的情况下,所有Unordered_set操作都是O(1)和O(n),但通常保持不变(https://www.geeksforgeeks.org/unordered_set-in-cpp-stl/)。在您的例子中,您需要迭代两次数组,所以它将是O(n2)。在这种情况下,您可以迭代数组一次O(n)并使用O(1) set操作,因此这将是一个更快的解决方案:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[10] = {1, 9, 7, 8, 9, 6, 9, 8, 7, 1};
unordered_set<int> numbersSet;
unordered_set<int> duplicateSet;
int duplicatesCount = 0;
for (size_t i = 0; i < 10; i++)
{
int number = arr[i];
numbersSet.insert(number);
if (numbersSet.find(number) != numbersSet.end())
{
duplicatesCount++;
duplicateSet.insert(number);
}
}
cout << "\nAll elements duplicated : ";
unordered_set<int>::iterator itr;
for (itr = duplicateSet.begin(); itr != duplicateSet.end(); itr++)
cout << (*itr) << endl;
return 0;
}
All elements duplicated : 6
8
7
9
1
发布于 2022-05-01 08:18:02
int main()
{
const int SIZE = 10;
int arr[SIZE] = {1, 9, 7, 8, 9, 6, 9, 8, 7, 1};
int find[SIZE] = {0};
int repeat[SIZE] = {0};
int temp;
for (int i = 0; i < SIZE; i++)
{
temp = arr[i];
for (int j = 0; j < SIZE; j++)
{
if (i == j)
continue;
else{
if (temp == arr[j])
{
find[i] = temp;
repeat[j]++;
}
}
}
}
for (int i = 0; i < SIZE; i++)
cout << arr[i] << ' ';
cout << endl;
for (int i = 0; i < SIZE; i++)
cout << find[i] << ' ';
cout << endl;
for (int i = 0; i < SIZE; i++)
cout << repeat[i] + 1 << ' ';
system("pause");
return 0;
}
https://stackoverflow.com/questions/72077408
复制相似问题