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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2488 天前的主题，其中的信息可能已经有所发展或是发生改变。

题目描述

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

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

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

输入

输入包含多组测试用例。

每组测试用例中第一行为一个正整数 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

谢谢

筷子

输出

长度

数字

39 条回复 • 2018-02-20 23:18:02 +08:00

greenhat233

2018-02-18 23:28:11 +08:00 via Android

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

skadi

2018-02-18 23:58:05 +08:00

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

map[ element ]++;

monkeymonkey

2018-02-19 00:02:48 +08:00

```
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

2018-02-19 00:09:11 +08:00

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

x86vk

2018-02-19 00:15:37 +08:00 via Android

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

vegito2002

2018-02-19 00:19:07 +08:00

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

Yourshell

2018-02-19 00:20:23 +08:00 via Android

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

di94sh

2018-02-19 01:19:42 +08:00 via Android

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

Mirage09

2018-02-19 01:47:23 +08:00 via iPhone

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

hackpro

2018-02-19 02:26:38 +08:00 via iPhone

@vegito2002 厉害！

greenhat233

2018-02-19 02:35:40 +08:00 via Android

@skadi 主要是想熟悉下 set

greenhat233

2018-02-19 02:37:38 +08:00 via Android

@Yourshell 是某个 oj 里面的

greenhat233

2018-02-19 02:38:19 +08:00 via Android

@x86vk 主要是想熟悉下 set

wallriding

2018-02-19 03:45:40 +08:00

楼主你要的用 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

2018-02-19 08:54:00 +08:00 via Android

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

SuperFashi

2018-02-19 08:58:17 +08:00 via Android

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

x86vk

2018-02-19 09:15:50 +08:00 via Android

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

vegito2002

2018-02-19 10:21:32 +08:00

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

kiwi95

2018-02-19 10:29:55 +08:00 via iPhone

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

SuperFashi

2018-02-19 12:15:07 +08:00 via Android

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

vegito2002

2018-02-19 12:21:49 +08:00

@SuperFashi 数组是在你知道筷子长度值域的情况下才行吧, 否则对于空间的浪费完全不可控

vegito2002

2018-02-19 12:22:32 +08:00

@SuperFashi 哦没注意看, 还真的给了值域. 大概扫了题目一眼就写了, 没仔细看

SuperFashi

2018-02-19 12:22:53 +08:00 via Android

@vegito2002 筷子长度范围给了的，小得很。其实严谨来说空间是 O(L)

geelaw

2018-02-19 13:12:39 +08:00 via iPhone

@kiwi95
@vegito2002
@SuperFashi

可是长度范围比筷子个数大不少呀。当然这个问题用计数法可能很快，然而在这些数具体给定的情况下还是要用实践看看哪个方法更适合 AC。

另，这样做是 L 的时间而不是 N 的时间，实践中可能更快 /很快是因为 L 前面的因数比较小的缘故吧。

vegito2002

2018-02-19 13:27:38 +08:00

@geelaw 我回头想想, 楼主这里是不是复制的时候丢了指数? 他这里复制的是筷子长度最长 109, 如果真的是这个完全是可以当成 O(1)空间的 counting 的. 但是我觉得很有可能楼主这里这两个数字实际上是 10^9 和 10^6, 只是他自己复制的时候忘记修正一下. 如果真的是指数级别, 那肯定就必须用 Map 了, 要合理利用 sparsity, bucket counting 会浪费太多的空间;

当然, 具体情况还是要看这个东西用在什么场合了; 从做题的角度反正是我就一个 Map 搞定算了, 面试官不让我用 bucket 我就先不走这个优化;

vegito2002

2018-02-19 13:28:50 +08:00

@geelaw 如果是他们的 2pass 的做法, 那么确实如果 N=O(L), 那么 bucket 的 count 做法会导致最后的时间是 O(L). 但是如果采用我 6L 的代码, 还是一个 O(N)的时间, 因为不需要重新分析一次 count;

x86vk

2018-02-19 13:57:15 +08:00 via Android

@vegito2002 弱弱的问一句 map 插入查找不是 logn 嘛

vegito2002

2018-02-19 14:09:10 +08:00

@x86vk 我不是百分百清楚, 不过 LeetCode 讨论区看到过有人说好像跟语言有关系;

http://www.cplusplus.com/forum/general/31927/

如果是 c++, 你说的是对的; java 的话, 好像 Map 操作都能当 O(1)来玩;

上面那个帖子我没仔细读完, 主要是我也没有正经学过 c++, 一些语言特性不太清楚;

geelaw

2018-02-19 14:28:09 +08:00

@vegito2002 #25 显然是 10^6 和 10^9。但无论如何这是一个常数，只能说是很大的常数吧。

@vegito2002 #26 初始化 count 已经需要 Omega(L) 的时间。

@vegito2002 #28 C++ 的 std::map 需要 O(logn) 的时间查找； Java 的 Map 是 **期望** O(1)。

vegito2002

2018-02-19 14:30:32 +08:00

@geelaw 初始化确实是, 只要用 bucket 方法就少不了 O(L), 同意

x86vk

2018-02-19 14:37:35 +08:00 via Android

@vegito2002 java 如果您指的是 hashmap 的话，精心构造的数据理论上是不是可以把它搞成 on 的查找和插入

vegito2002

2018-02-19 14:40:03 +08:00

@x86vk 当然是可以的, hash 从来都不是万无一失的

zjuturtle

2018-02-19 17:12:26 +08:00

leetcode 上有这道题目
https://leetcode.com/problems/single-number-ii/description/
时间复杂度 O(n)
空间复杂度 O(1)

using namespace std;
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int tmp=0,tmp1=1,numA=0,numB=0;
for (auto it = nums.begin(); it != nums.end(); it++) {
tmp ^= (*it);
}
while (tmp % 2 == 0) {
tmp1 *= 2;
tmp /= 2;
}

for (auto it = nums.begin(); it != nums.end(); it++) {
if ((tmp1 ^ (*it)) == ((*it)-tmp1)) {
numA ^= (*it);
}
else {
numB ^= (*it);
}
}
auto res = new vector<int>;
(*res).push_back(numA);
(*res).push_back(numB);
return *res;
}
};

zjuturtle

2018-02-19 17:13:27 +08:00

@zjuturtle 日贴错了，应该是这个

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> positiveCounts(32, 0);
vector<int> negtiveCounts(32, 0);
for (auto it = nums.begin(); it != nums.end(); it++) {
auto tmp = *it;
int index = 0;
if (tmp > 0) {
while (tmp!=0) {
positiveCounts[index] += (tmp % 2);
tmp /= 2;
index++;
}
}
else {
tmp = -tmp;
while (tmp != 0) {
negtiveCounts[index] += (tmp % 2);
tmp /= 2;
index++;
}
}
}
int pos = 0,neg=0,p=1,n=1;
for (int i = 0; i < 32; i++) {
auto pbit = positiveCounts[i] %= 3;
auto nbit = negtiveCounts[i] %= 3;
pos += (pbit*p);
neg += (nbit*n);
p *= 2;
n *= 2;
}
if(pos>0)
return pos;
return -neg;
}
};

zjuturtle

2018-02-19 17:17:07 +08:00

@zjuturtle 日原题有很多变种我特么又贴错了，给跪。
原题
https://leetcode.com/problems/single-number/description/
解答
#include<iostream>
#include<vector>

using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto it = nums.begin(); it != nums.end(); it++) {
res ^= *it;
}
return res;
}
};

starqoq

2018-02-19 21:53:20 +08:00

第一问是 (N-1)/2
第二问是所有数字 xor 一下，成对的数字 xor 两次等于零。

vegito2002

2018-02-19 23:10:33 +08:00

@starqoq 1112222 (N - 1) / 2 = 3, 但是要求的是种类数量, 应该是 2;

starqoq

2018-02-20 16:24:28 +08:00

@vegito2002
7
[1 1] 1 [2 2] [2 2]
这样不是能凑三双？

vegito2002

2018-02-20 23:18:02 +08:00

@starqoq 看楼主 1L 的帖子, 这个例子应该返回 2, 因为只有两**种**.