题目描述
小陈上了一天的课后,走在回宿舍的路上。走着走着,突然发现前面一位食堂的阿姨一不小心把刚洗好的筷子打翻了。
小陈很热心,于是飞快地走上前去帮她捡。阿姨说:“谢谢你哈!但是,这些筷子都乱了,你能帮我把它们凑成一对一对的吗?啊!对了,里面还有一只筷子是落单的。帮我把它找出来吧!谢谢你哈”(哇……你要求怎么这么多)
请你帮忙数一下一共有多少双筷子并找出那只落单的筷子吧!
输入
输入包含多组测试用例。
每组测试用例中第一行为一个正整数 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
谢谢
1
greenhat233 OP 输入那里是
5 1 2 3 1 2 7 1 1 1 2 2 2 2 输出是 2 3 2 1 |
2
skadi 2018-02-18 23:58:05 +08:00 1
惊了.直接一个 map 就解决了的事情.
map[ element ]++; |
3
monkeymonkey 2018-02-19 00:02:48 +08:00 1
```
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; } ``` |
4
vegito2002 2018-02-19 00:09:11 +08:00 4
所有筷子长度异或到一起, 结果就是落单筷子的长度
|
5
x86vk 2018-02-19 00:15:37 +08:00 via Android 1
其实没必要那么复杂吧,直接全部读入后排序,从头到尾撸一遍就行。复杂度 nlogn
|
6
vegito2002 2018-02-19 00:19:07 +08:00 1
落单筷子长度=0;
map count; 筷子种类数; for each 筷子 { 落单筷子长度 ^= 这个筷子长度; if (count[这个筷子长度]++ == 0): 筷子种类数++; } if (--count[落单筷子长度] == 0): 筷子种类数--; return (落单筷子长度, 筷子种类数); |
7
Yourshell 2018-02-19 00:20:23 +08:00 via Android
我觉得和编程珠玑第一章那个问题挺像的。你的代码我就看不懂了
|
8
di94sh 2018-02-19 01:19:42 +08:00 via Android
建一个 map 长度为键:该长度个数为值 如果为奇数就是落单的。
|
9
Mirage09 2018-02-19 01:47:23 +08:00 via iPhone 1
排序后遍历一遍,奇数个就是落单的。
|
10
hackpro 2018-02-19 02:26:38 +08:00 via iPhone
@vegito2002 厉害!
|
11
greenhat233 OP @skadi 主要是想熟悉下 set
|
12
greenhat233 OP @Yourshell 是某个 oj 里面的
|
13
greenhat233 OP @x86vk 主要是想熟悉下 set
|
14
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; } |
15
SuperFashi 2018-02-19 08:54:00 +08:00 via Android
@vegito2002 正解,时间 O(n)空间 O(1)
|
16
SuperFashi 2018-02-19 08:58:17 +08:00 via Android
等,不一定,如果要算种类那还不如直接 hashmap
|
17
x86vk 2018-02-19 09:15:50 +08:00 via Android
@SuperFashi set 我记得查找是 logn 啊,如果套哈希的话数据可以把你卡成 n2 的复杂度
|
18
vegito2002 2018-02-19 10:21:32 +08:00
@SuperFashi 我 6L 的代码是 O(N)时间而且是 1-pass. 这题 O(1)空间是做不到的, 只能抢一个常数因子的时间差距; 只用 count 来做的话, 我觉得可能要两个 pass? 筷子本身过一个 pass, 然后 count 要过一个 pass;
|
19
kiwi95 2018-02-19 10:29:55 +08:00 via iPhone
筷子的长度取值空间这么小,一个位图表示,空间和 N 没有关系,可以看成 O(1)的空间,O(n)的时间,类似 6L 的方法
|
20
SuperFashi 2018-02-19 12:15:07 +08:00 via Android
@vegito2002 不用 map,直接数组就行
|
21
vegito2002 2018-02-19 12:21:49 +08:00
@SuperFashi 数组是在你知道筷子长度值域的情况下才行吧, 否则对于空间的浪费完全不可控
|
22
vegito2002 2018-02-19 12:22:32 +08:00
@SuperFashi 哦没注意看, 还真的给了值域. 大概扫了题目一眼就写了, 没仔细看
|
23
SuperFashi 2018-02-19 12:22:53 +08:00 via Android
@vegito2002 筷子长度范围给了的,小得很。其实严谨来说空间是 O(L)
|
24
geelaw 2018-02-19 13:12:39 +08:00 via iPhone
@kiwi95
@vegito2002 @SuperFashi 可是长度范围比筷子个数大不少呀。当然这个问题用计数法可能很快,然而在这些数具体给定的情况下还是要用实践看看哪个方法更适合 AC。 另,这样做是 L 的时间而不是 N 的时间,实践中可能更快 /很快是因为 L 前面的因数比较小的缘故吧。 |
25
vegito2002 2018-02-19 13:27:38 +08:00
@geelaw 我回头想想, 楼主这里是不是复制的时候丢了指数? 他这里复制的是筷子长度最长 109, 如果真的是这个完全是可以当成 O(1)空间的 counting 的. 但是我觉得很有可能楼主这里这两个数字实际上是 10^9 和 10^6, 只是他自己复制的时候忘记修正一下. 如果真的是指数级别, 那肯定就必须用 Map 了, 要合理利用 sparsity, bucket counting 会浪费太多的空间;
当然, 具体情况还是要看这个东西用在什么场合了; 从做题的角度反正是我就一个 Map 搞定算了, 面试官不让我用 bucket 我就先不走这个优化; |
26
vegito2002 2018-02-19 13:28:50 +08:00
@geelaw 如果是他们的 2pass 的做法, 那么确实如果 N=O(L), 那么 bucket 的 count 做法会导致最后的时间是 O(L). 但是如果采用我 6L 的代码, 还是一个 O(N)的时间, 因为不需要重新分析一次 count;
|
27
x86vk 2018-02-19 13:57:15 +08:00 via Android
@vegito2002 弱弱的问一句 map 插入查找不是 logn 嘛
|
28
vegito2002 2018-02-19 14:09:10 +08:00
@x86vk 我不是百分百清楚, 不过 LeetCode 讨论区看到过有人说好像跟语言有关系;
http://www.cplusplus.com/forum/general/31927/ 如果是 c++, 你说的是对的; java 的话, 好像 Map 操作都能当 O(1)来玩; 上面那个帖子我没仔细读完, 主要是我也没有正经学过 c++, 一些语言特性不太清楚; |
29
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)。 |
30
vegito2002 2018-02-19 14:30:32 +08:00
@geelaw 初始化确实是, 只要用 bucket 方法就少不了 O(L), 同意
|
31
x86vk 2018-02-19 14:37:35 +08:00 via Android
@vegito2002 java 如果您指的是 hashmap 的话,精心构造的数据理论上是不是可以把它搞成 on 的查找和插入
|
32
vegito2002 2018-02-19 14:40:03 +08:00
@x86vk 当然是可以的, hash 从来都不是万无一失的
|
33
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; } }; |
34
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; } }; |
35
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; } }; |
36
starqoq 2018-02-19 21:53:20 +08:00
第一问是 (N-1)/2
第二问是 所有数字 xor 一下,成对的数字 xor 两次等于零。 |
37
vegito2002 2018-02-19 23:10:33 +08:00
@starqoq 1112222 (N - 1) / 2 = 3, 但是要求的是种类数量, 应该是 2;
|
38
starqoq 2018-02-20 16:24:28 +08:00
|
39
vegito2002 2018-02-20 23:18:02 +08:00
@starqoq 看楼主 1L 的帖子, 这个例子应该返回 2, 因为只有两**种**.
|