一道简单的 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

谢谢

[vegito2002]

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

[vegito2002]

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

[SuperFashi]

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

[geelaw]

@kiwi95
@vegito2002
@SuperFashi

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

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

[vegito2002]

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

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

[vegito2002]

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

[x86vk]

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

[vegito2002]

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

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

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

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

[geelaw]

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

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

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

[vegito2002]

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

[x86vk]

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

[vegito2002]

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

[zjuturtle]

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]

@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]

@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]

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

[vegito2002]

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

[starqoq]

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

[vegito2002]

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