使用哈希图打印第一个重复元素;

Question

#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<int,int>h;
int T;
int n,i;
cin>>T;
while(T--)
{  int flag=0;
cin>>n;
int arr[n];
for( i=0;i<n;i++)
{
cin>>arr[i];
}
for(i=0;i<n;i++)
{
h[i]=count(arr,arr+n,arr[i]);
}
for(auto x: h)
{
if(x.second>1)
{ flag=1;
cout<<x.first<<endl;
break;
}
}
if(flag==0)
{  cout<<-1<<endl;
}
}
}

给定一个整数数组。任务是找到数组中的第一个重复元素，即多次出现且首次出现的索引最小的元素。

我得到了无限的结果。 我什么没有错。 测试用例如下

输入：

test case :1 
array size:7 
array(1 5 3 4 2 4 5 ) 

输出：

2

Answer 1

由于您使用的是std::unordered_map，该方法应该非常简单：

Set the minimum position to a large value.
Loop on the number data from first item to last.
If the number does not exist in the map, then 
Add the item and position to the map
else
Set the minimum position to min(minimum position, position found in map)

不需要flag变量(这几乎总是会导致某处出现问题，并且很可能是错误的原因(，也不需要像这样一遍又一遍地重新计算原始数组中的项目：

for(i=0;i<n;i++)
{
h[i]=count(arr,arr+n,arr[i]);
}

如果您有 1000 个号码，您将调用此计数循环 1000 次。 这是非常低效的。

至于您的实现，您将第一个副本的索引存储在哪里？ 我没有看到它，除非它隐藏在你用这个flag变量进行的所有操作后面。 无论你在做什么，都是错误的。

---

下面是一个实现，使用您的测试数据和我之前介绍的大纲：

#include <unordered_map>
#include <iostream>
#include <algorithm>
#include <climits>
int main() 
{
std::unordered_map<int, int> numbers;
int test[] = {1, 5, 3, 4, 2, 4, 5}; 
// Set minimum index to a large value
int minIndex = std::numeric_limits<int>::max();
for (size_t i = 0; i < std::size(test); ++i )
{
// check if item is found
auto iter = numbers.find(test[i]);
if ( iter == numbers.end())
// not found, so add item and position 
numbers.insert({test[i], i});
else
// set the minimum index to the found position and exit the loop
minIndex = std::min(minIndex, iter->second);
}
if ( minIndex == std::numeric_limits<int>::max()) 
std::cout << -1;
else
std::cout << minIndex;
}

输出：

1

这实际上具有O(n)运行时，而不是您编写的内容，由于计数循环效率低下而O(n^2)。

Answer 2

尽管有问题，但这行代码

int arr[n];

不允许C++即使您的本地 IDE 没有给出任何错误，我认为您的在线判断会给出运行时错误。

由于C++中的数组必须是静态分配的，这意味着您需要在运行代码之前知道数组的元素数。