给定大小为N的数组a[]，其中包含从0到N-1的元素，您需要找到在给定数组中出现一次以上的所有元素。输入:N = 4A [] = {0,3,1,2}输出:1说明:N=4，所有元素从0开始到(N-1 = 3)存在于给定的数组中。因此输出为-1。
下面的解决方案有什么问题?
vector<int> duplicates(int arr[], int n) {
unordered_set<int> m;
vector<int> ans;
for(int i=0;i<n;i++){
//if element is found
if(m.find(arr[i])!=m.end())
ans.push_back(arr[i]);
//if element is not found
else
m.insert(arr[i]);
}
if(ans.empty())
ans.push_back(-1);
return ans;
}
如果一个值出现两次以上，则该解决方案返回不止一次。
例如，对于a = {1, 1, 1}，当正确答案为{1}时，它将返回{1, 1}。
解决方案有一个问题。对于集合中已经存在的每个值，您将把该值添加到结果中。如果有超过2个相同的值，那么您将总是将相同的值再次添加到结果向量中。
让我们看看下面的例子:{1,2,3,42,42,42,42}:
Loop
run value set vector
0 1 1 -
1 2 1,2 -
2 3 1,2,3 -
3 42 1,2,3,42 -
4 42 1,2,3,42 42 Duplicate found. Add to vector
5 42 1,2,3,42 42,42 Again duplicate found. Add again to vector
6 42 1,2,3,42 42,42,42 Again duplicate found. Add again to vector
所以，不幸的是，这个解决方案将不起作用。
你需要做的是找出一个值是否出现了不止一次。这可以通过计数来实现然后检查计数是否大于1然后将值添加到结果std::vector
计数的标准方法是使用std::unordered_map，我们可以将计数与每个值相关联。
首先计算所有值。然后，计算计数器，如果计数大于1，则将所有值加到结果向量中。
一个可能的解决方案是这样的:
#include <iostream>
#include <vector>
#include <unordered_map>
std::vector<int> duplicates(int arr[], int n) {
// Here we will count the occurence of each integer in the array
std::unordered_map<int, unsigned int> counter{};
// Do the counting
for (int i = 0; i < n; ++i)
counter[arr[i]]++;
// This will hold the result. Either the duplicates, or -1 of no duplicate
std::vector<int> result{};
// Check all counted values. If the counter is more than one for a vakue, add it (only one time to the result)
for (const auto& [value, count] : counter)
if (count > 1) result.push_back(value);
// If there was no duplicate, then add -1 to the vector
if (result.empty()) result.push_back(-1);
return result;
}
int main() {
int arr[]{ 0,1,2,3,42,42,42};
for (int i : duplicates(arr, sizeof(arr) / sizeof(arr[0])))
std::cout << i << ' ';
}
我将展示原始解决方案并注释。通过阅读评论，你将理解问题所在。
我建议你，尽可能多写评论。然后，您将在早期阶段自己发现问题。
#include <vector>
#include <iostream>
#include <unordered_set>
using namespace std;
vector<int> duplicates(int arr[], int n) {
// This set can contain only unique values
unordered_set<int> m;
// Here we will store the result
vector<int> ans;
// Iterate over all values in the array
for (int i = 0; i < n; i++) {
// Check, if the value from the array is already in the set
if (m.find(arr[i]) != m.end())
// Yes it is alread in the set
// So add it to the resulting answer
// **** But caveat: If there are 5 identical duplicates,
// we will add 4 times the value to the answer --> Bug
ans.push_back(arr[i]);
else
// If element is not found, so, was not yet present in the set, add it
m.insert(arr[i]);
}
// Special case for no duplicates
if (ans.empty())
ans.push_back(-1);
return ans;
}
int main() {
int arr[] {0,1,2,3,42,42,42,42,42};
for (int i : duplicates(arr, sizeof(arr)/sizeof(arr[0])))
cout << i << ' ';
}
Gassa正确地识别了一个bug。解决方法是在两次迭代中执行此操作，而不是尝试在数组的一次迭代中执行此操作。
这里有一个简单的方法来做到没有set。利用数组中所有元素都在0..之间这一事实N-1
vector<int> duplicates(int arr[], int n) {
vector<int> table; // tracks number of occurrences of a value in arr
vector<int> duplicates;
table.resize(n);
for (int i = 0; i < n; i++)
{
table[arr[i]]++;
}
for (int i = 0; i < n; i++)
{
if (table[i] > 1)
{
duplicates.push_back(i);
}
}
if (duplicates.size() == 0)
{
duplicates.push_back(-1);
}
return duplicates;
}
你可以一次完成。
std::vector<int> dups(int arr[], int n)noexcept {
int i;
std::vector<int> lut(n), ret;
for (i = 0; i != n; ++i) {
if (++lut[arr[i]] == 2) {
ret.emplace_back(arr[i]);
}
}
if (ret.empty()) {
ret.emplace_back(-1);
}
return ret;
}
lut[elem]给出了在arr中elem可用的次数。要成为重复元素，必须在至少一次以上可用。你只在乎第二次!第二次在arr中找到元素时，将其存储在ret中。