找筷子(chopsticks.cpp)

Question

答案不对
题目描述
经过一段时间的紧张筹备，电脑小组的“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;
}


//请大家看一下这题，谢谢，我不太会

Answer 1

一般对于超时的问题，都会选择用空间换时间的策略。这个题可以用一个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;
}