在c++中使用Set查找数组中的重复项

我目前正在练习编码面试，我正在研究一个函数，该函数接受一个数组和该数组的大小，并打印出其中哪些数字是重复的。我已经使用了两个for循环方法，但想要一个使用集合的优化解决方案。下面是我的代码片段

#include <iostream>
#include <set>
using namespace std;
void FindDuplicate(int integers[], int n){
set<int>setInt;
for(int i = 0; i < n; i++){
//if this num is not in the set then it is not a duplicate

if(setInt.find(integers[i]) != setInt.end()){
setInt.insert({integers[i]});
}
else
cout << integers[i] << " is a duplicate";
}
}
int main() {

int integers [] = {1,2,2,3,3};
int n = sizeof(integers)/sizeof(integers[0]);
FindDuplicate(integers, n);
}

任何有用的建议都是感激的，谢谢

我认为你的比较不需要，插入为你做:https://en.cppreference.com/w/cpp/container/set/insert

返回一个由迭代器组成的指向插入元素(或)的pair到阻止插入的元素)，并将bool值设置为如果插入发生，则为True。

插入元素并检查插入函数返回的结果(如果pair的第二个元素重复，则返回false):)

我的解决方案是:

计算每个元素的频率(这里解释了频率的算法)。
显示频率大于1的元素(它是重复的)

在每个操作中，不要使用叠叠循环。

#include <iostream>
#include <unordered_map>
using namespace std;
void FindDuplicate(int integers[], int n)
{
unordered_map<int, int> mp;
// Traverse through array elements and
// count frequencies
for (int i = 0; i < n; i++)
{
mp[integers[i]]++;
}
cout << "The repeating elements are : " << endl;
for (int i = 0; i < n; i++) {
if (mp[integers[i]] > 1)
{
cout << integers[i] << endl;
mp[integers[i]] = -1;
}
}
}
int main()
{
int integers [] = {1,1,0,0,2,2,3,3,3,6,7,7,8};
int n = sizeof(integers)/sizeof(integers[0]);
FindDuplicate(integers, n);
}

这是我的反馈:

#include <iostream>
#include <vector>
#include <set>
// dont' do this, in big projects it's not done (nameclash issues)
// using namespace std;
// pass vector by const reference you're not supposed to change the input
// the reference will prevent data from being copied.
// naming is important, do you want to find one duplicate or more...
// renamed to FindDuplicates because you want them all
void FindDuplicates(const std::vector<int>& input) 
{
std::set<int> my_set;     
// don't use index based for loops if you don't have to
// range based for loops are more safe
// const auto is more refactorable then const int
for (const auto value : input)
{
//if (!my_set.contains(value)) C++ 20 syntax 
if (my_set.find(value) == my_set.end())
{
my_set.insert(value);
}
else
{
std::cout << "Array has a duplicate value : " << value << "n";
}
}
}
int main() 
{
// int integers[] = { 1,2,2,3,3 }; avoid "C" style arrays they're a **** to pass around safely
// int n = sizeof(integers) / sizeof(integers[0]); std::vector (or std::array) have size() methods 
std::vector input{ 1,2,2,3,3 };
FindDuplicates(input);
}

您不需要使用集合。查找重复项:

排序数组
遍历数组(从第二个元素开始)并将前一个元素等于
当前元素的元素复制到一个新向量中;
(可选)在"duplicate "上使用unique如果您想知道哪个数字是重复的，而不关心它是数字数组中的2,3或4次

示例实现:

#include <algorithm>
#include <iostream>
#include <vector>
void
printVector (std::vector<int> const &numbers)
{
for (auto const &number : numbers)
{
std::cout << number << ' ';
}
std::cout << std::endl;
}
int
main ()
{
auto numbers = std::vector<int>{ 1, 2, 2, 42, 42, 42, 3, 3, 42, 42, 1, 2, 3, 4, 5, 6, 7, 7 };
std::sort (numbers.begin (), numbers.end ());
auto duplicates = std::vector<int>{};
std::for_each (numbers.begin () + 1, numbers.end (), [prevElement = numbers.begin (), &duplicates] (int currentElement) mutable {
if (currentElement == *prevElement)
{
duplicates.push_back (currentElement);
}
prevElement++;
});
duplicates.erase (std::unique (duplicates.begin (), duplicates.end ()), duplicates.end ());
printVector (duplicates);
}

编辑:如果您不介意使用更多内存和更多计算，但希望它更具表现力:

<<ol>

排序数字/gh>

创建一个具有唯一数字的新数组"uniqueNumbers">

使用"set_difference"计算(numbers-uniqueNumbers)，生成一个包含所有重复项的新数组

(可选)在"duplicate "上使用unique如果您想知道哪个数字是重复的，而不关心它是数字数组中的2,3或4次示例实现:

#include <algorithm>
#include <iostream>
#include <vector>
void
printVector (std::vector<int> const &numbers)
{
for (auto const &number : numbers)
{
std::cout << number << ' ';
}
std::cout << std::endl;
}
int
main ()
{
auto numbers = std::vector<int>{ 2, 2, 42, 42, 42, 3, 3, 42, 42, 1, 2, 3, 4, 5, 6, 7, 7 };
std::sort (numbers.begin (), numbers.end ());
auto uniqueNumbers = std::vector<int>{};
std::unique_copy (numbers.begin (), numbers.end (), std::back_inserter (uniqueNumbers));
auto duplicates = std::vector<int>{};
std::set_difference (numbers.begin (), numbers.end (), uniqueNumbers.begin (), uniqueNumbers.end (), std::back_inserter (duplicates));
std::cout << "duplicate elements: ";
printVector (duplicates);
std::cout << "unique duplicate elements: ";
printVector ({ duplicates.begin (), std::unique (duplicates.begin (), duplicates.end ()) });
}

这里有一个快速的解决方案使用大小为N的数组(尝试一个大数字)当一个数字被添加到大数组的另一个数组时，在位置上加1，如下所示:array_of_repeated [user_input] + +;因此，如果程序询问(例如)数字234被重复了多少次?std:: cout<& lt; array_of_repeated [requested_number] & lt; & lt; std:: endl;这样你就不用花时间在另一个列表

中查找数字了

相关内容

最新更新

热门标签：