一道简单的 c++编程题求解答

[greenhat233]

题目描述

小陈上了一天的课后，走在回宿舍的路上。走着走着，突然发现前面一位食堂的阿姨一不小心把刚洗好的筷子打翻了。

小陈很热心，于是飞快地走上前去帮她捡。阿姨说：“谢谢你哈！但是，这些筷子都乱了，你能帮我把它们凑成一对一对的吗？啊！对了，里面还有一只筷子是落单的。帮我把它找出来吧！谢谢你哈”（哇……你要求怎么这么多）

请你帮忙数一下一共有多少双筷子并找出那只落单的筷子吧！

输入

输入包含多组测试用例。

每组测试用例中第一行为一个正整数 N，代表筷子的只数。（ 1≤N≤5×106 ）

接下来一行有 N 个正整数，代表筷子的长度 Li （ 1≤Li≤109 ）。

输出

对于每组测试用例，输出两个数字。

第一个数字为能凑成的不同长度的筷子的种类数，第二个数字是落单的筷子的长度。这两个数字用一个空格隔开。

样例输入

5 1 2 3 1 2 7 1 1 1 2 2 2 2

样例输出

2 3 2 1 下面是我的代码: https://paste.ubuntu.com/p/RJ7TFZ6fVD/ 思路是先存放在 multiset，然后用 count()查看容器里面每个值的个数，每处理完一个，就删除掉，处理下一个，但是 erase 那里出了问题，我不知道是什么问题，麻烦 v 友解答下。

下面给出一个失败输出样例: 43 31 9 3 8 12 22 13 18 16 23 1 21 20 26 25 4 27 30 11 15 31 9 3 8 12 22 13 18 16 23 1 21 20 26 25 7 4 27 30 11 15 15 15

谢谢

[greenhat233]

输入那里是
5
1 2 3 1 2
7
1 1 1 2 2 2 2
输出是
2 3
2 1

[skadi]

惊了.直接一个 map 就解决了的事情.

map[ element ]++;

[monkeymonkey]

```
int main()
{
int N = 0;
int hash[1000] = {0};
int l = 0;

cin >> N;
for (int i = 0; i < N; i++) {
cin >> l;
hash[l]++;
}

int count = 0, single = 0;
for (int i = 0; i < 1000; i++) {
if (hash[i] >= 2)
count++;
if (hash[i] % 2 != 0)
single = i;
}

cout << count << " " << single << endl;
return 0;
}
```

[vegito2002]

所有筷子长度异或到一起, 结果就是落单筷子的长度

[x86vk]

其实没必要那么复杂吧，直接全部读入后排序，从头到尾撸一遍就行。复杂度 nlogn

[vegito2002]

落单筷子长度=0;
map count;
筷子种类数;
for each 筷子
{
落单筷子长度 ^= 这个筷子长度;
if (count[这个筷子长度]++ == 0): 筷子种类数++;
}
if (--count[落单筷子长度] == 0): 筷子种类数--;
return (落单筷子长度, 筷子种类数);

[Yourshell]

我觉得和编程珠玑第一章那个问题挺像的。你的代码我就看不懂了

[di94sh]

建一个 map 长度为键：该长度个数为值 如果为奇数就是落单的。

[Mirage09]

排序后遍历一遍，奇数个就是落单的。

[hackpro]

@vegito2002 厉害！

[greenhat233]

@skadi 主要是想熟悉下 set

[greenhat233]

@Yourshell 是某个 oj 里面的

[greenhat233]

@x86vk 主要是想熟悉下 set

[wallriding]

楼主你要的用 set 的方法

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
unordered_set<int> singles;
unordered_set<int> pairs;
int N = 0;
cin >> N;
for (int i = 0; i < N; i++) {
int l;
cin >> l;
if (singles.find(l) == singles.end()) {
singles.insert(l);
}
else {
singles.erase(l);
pairs.insert(l);
}
}
cout << pairs.size() << " " << *singles.begin() << endl;
return 0;
}

[SuperFashi]

@vegito2002 正解，时间 O(n)空间 O(1)

[SuperFashi]

等，不一定，如果要算种类那还不如直接 hashmap

[x86vk]

@SuperFashi set 我记得查找是 logn 啊，如果套哈希的话数据可以把你卡成 n2 的复杂度

[vegito2002]

@SuperFashi 我 6L 的代码是 O(N)时间而且是 1-pass. 这题 O(1)空间是做不到的, 只能抢一个常数因子的时间差距; 只用 count 来做的话, 我觉得可能要两个 pass? 筷子本身过一个 pass, 然后 count 要过一个 pass;

[kiwi95]

筷子的长度取值空间这么小，一个位图表示，空间和 N 没有关系，可以看成 O(1)的空间，O(n)的时间，类似 6L 的方法

[SuperFashi]

@vegito2002 不用 map，直接数组就行