答案不对
题目描述
经过一段时间的紧张筹备，电脑小组的“RP餐厅”终于开业了，这天，经理LXC接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题，筷子！CX小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是CX找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮CX找出这只落单的筷子吗？
输入格式
第一行读入一个数N，它代表CX找到的筷子的根数。第二行是N个用空格隔开的整数，代表筷子的长度。
输出格式
落单的筷子的长度以及它的数量，用一个空格隔开。
样例
输入#1
9
2 2 1 3 3 3 2 3 1
Copy
输出#1
2 3
Copy
数据范围
对于100%的数据，1 ≤ 筷子长度 ≤ 100
对于30%的数据，10 ≤ N ≤ 2,000
对于60%的数据，10 ≤ N ≤ 2,000,0
对于100%的数据，10 ≤ N ≤ 2,000,000
思考
对于100%的测试数据，输入数据量很大，输入数据会很耗时。如何不超时呢？
#include<bits/stdc++.h>
using namespace std;
int a[2001]={0};
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
long long n,f=0;
cin>> n;
for(int i = 1;i <= n; i++ )
{
cin>>a[i];
}int j;
for(int i = 1;i <= n; i++ )
{
j=i+1;
for(j=i+1;j<=n;j++)
{
if(f==1)
{
j=n+1;
}
if(a[i]==a[j])
{
a[i]=0;a[j]=0;f=1;
}
}
}
for(int i=1;i<=n;i++)
{
if(a[i]!=0)
{
cout<<a[i]<<" ";
}
}
return 0;
}
//请大家看一下这题，谢谢，我不太会
一般对于超时的问题，都会选择用空间换时间的策略。这个题可以用一个map存储每种长度筷子出现的次数，然后找到出现次数为1的筷子即可，时间复杂度为O(n).代码如下，望采纳
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
int n;
cin >> n;
unordered_map<int, int> cnt; // 存储每个长度出现的次数
for (int i = 0; i < n; i++) {
int l;
cin >> l;
cnt[l]++;
}
for (auto p : cnt) { // 遍历所有长度，找到出现次数为1的那一个
if (p.second == 1) {
cout << p.first << " " << p.second << endl;
break;
}
}
return 0;
}