V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
greenhat233
V2EX  ›  问与答

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

  •  
  •   greenhat233 · 2018-02-18 23:26:55 +08:00 via Android · 4078 次点击
    这是一个创建于 2230 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目描述

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

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

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

    输入

    输入包含多组测试用例。

    每组测试用例中第一行为一个正整数 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
        1
    greenhat233  
    OP
       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
        2
    skadi  
       2018-02-18 23:58:05 +08:00   ❤️ 1
    惊了.直接一个 map 就解决了的事情.

    map[ element ]++;
    monkeymonkey
        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;
    }
    ```
    vegito2002
        4
    vegito2002  
       2018-02-19 00:09:11 +08:00   ❤️ 4
    所有筷子长度异或到一起, 结果就是落单筷子的长度
    x86vk
        5
    x86vk  
       2018-02-19 00:15:37 +08:00 via Android   ❤️ 1
    其实没必要那么复杂吧,直接全部读入后排序,从头到尾撸一遍就行。复杂度 nlogn
    vegito2002
        6
    vegito2002  
       2018-02-19 00:19:07 +08:00   ❤️ 1
    落单筷子长度=0;
    map count;
    筷子种类数;
    for each 筷子
    {
    落单筷子长度 ^= 这个筷子长度;
    if (count[这个筷子长度]++ == 0): 筷子种类数++;
    }
    if (--count[落单筷子长度] == 0): 筷子种类数--;
    return (落单筷子长度, 筷子种类数);
    Yourshell
        7
    Yourshell  
       2018-02-19 00:20:23 +08:00 via Android
    我觉得和编程珠玑第一章那个问题挺像的。你的代码我就看不懂了
    di94sh
        8
    di94sh  
       2018-02-19 01:19:42 +08:00 via Android
    建一个 map 长度为键:该长度个数为值 如果为奇数就是落单的。
    Mirage09
        9
    Mirage09  
       2018-02-19 01:47:23 +08:00 via iPhone   ❤️ 1
    排序后遍历一遍,奇数个就是落单的。
    hackpro
        10
    hackpro  
       2018-02-19 02:26:38 +08:00 via iPhone
    @vegito2002 厉害!
    greenhat233
        11
    greenhat233  
    OP
       2018-02-19 02:35:40 +08:00 via Android
    @skadi 主要是想熟悉下 set
    greenhat233
        12
    greenhat233  
    OP
       2018-02-19 02:37:38 +08:00 via Android
    @Yourshell 是某个 oj 里面的
    greenhat233
        13
    greenhat233  
    OP
       2018-02-19 02:38:19 +08:00 via Android
    @x86vk 主要是想熟悉下 set
    wallriding
        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;
    }
    SuperFashi
        15
    SuperFashi  
       2018-02-19 08:54:00 +08:00 via Android
    @vegito2002 正解,时间 O(n)空间 O(1)
    SuperFashi
        16
    SuperFashi  
       2018-02-19 08:58:17 +08:00 via Android
    等,不一定,如果要算种类那还不如直接 hashmap
    x86vk
        17
    x86vk  
       2018-02-19 09:15:50 +08:00 via Android
    @SuperFashi set 我记得查找是 logn 啊,如果套哈希的话数据可以把你卡成 n2 的复杂度
    vegito2002
        18
    vegito2002  
       2018-02-19 10:21:32 +08:00
    @SuperFashi 我 6L 的代码是 O(N)时间而且是 1-pass. 这题 O(1)空间是做不到的, 只能抢一个常数因子的时间差距; 只用 count 来做的话, 我觉得可能要两个 pass? 筷子本身过一个 pass, 然后 count 要过一个 pass;
    kiwi95
        19
    kiwi95  
       2018-02-19 10:29:55 +08:00 via iPhone
    筷子的长度取值空间这么小,一个位图表示,空间和 N 没有关系,可以看成 O(1)的空间,O(n)的时间,类似 6L 的方法
    SuperFashi
        20
    SuperFashi  
       2018-02-19 12:15:07 +08:00 via Android
    @vegito2002 不用 map,直接数组就行
    vegito2002
        21
    vegito2002  
       2018-02-19 12:21:49 +08:00
    @SuperFashi 数组是在你知道筷子长度值域的情况下才行吧, 否则对于空间的浪费完全不可控
    vegito2002
        22
    vegito2002  
       2018-02-19 12:22:32 +08:00
    @SuperFashi 哦没注意看, 还真的给了值域. 大概扫了题目一眼就写了, 没仔细看
    SuperFashi
        23
    SuperFashi  
       2018-02-19 12:22:53 +08:00 via Android
    @vegito2002 筷子长度范围给了的,小得很。其实严谨来说空间是 O(L)
    geelaw
        24
    geelaw  
       2018-02-19 13:12:39 +08:00 via iPhone
    @kiwi95
    @vegito2002
    @SuperFashi

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

    另,这样做是 L 的时间而不是 N 的时间,实践中可能更快 /很快是因为 L 前面的因数比较小的缘故吧。
    vegito2002
        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 我就先不走这个优化;
    vegito2002
        26
    vegito2002  
       2018-02-19 13:28:50 +08:00
    @geelaw 如果是他们的 2pass 的做法, 那么确实如果 N=O(L), 那么 bucket 的 count 做法会导致最后的时间是 O(L). 但是如果采用我 6L 的代码, 还是一个 O(N)的时间, 因为不需要重新分析一次 count;
    x86vk
        27
    x86vk  
       2018-02-19 13:57:15 +08:00 via Android
    @vegito2002 弱弱的问一句 map 插入查找不是 logn 嘛
    vegito2002
        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++, 一些语言特性不太清楚;
    geelaw
        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)。
    vegito2002
        30
    vegito2002  
       2018-02-19 14:30:32 +08:00
    @geelaw 初始化确实是, 只要用 bucket 方法就少不了 O(L), 同意
    x86vk
        31
    x86vk  
       2018-02-19 14:37:35 +08:00 via Android
    @vegito2002 java 如果您指的是 hashmap 的话,精心构造的数据理论上是不是可以把它搞成 on 的查找和插入
    vegito2002
        32
    vegito2002  
       2018-02-19 14:40:03 +08:00
    @x86vk 当然是可以的, hash 从来都不是万无一失的
    zjuturtle
        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;
    }
    };
    zjuturtle
        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;
    }
    };
    zjuturtle
        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;
    }
    };
    starqoq
        36
    starqoq  
       2018-02-19 21:53:20 +08:00
    第一问是 (N-1)/2
    第二问是 所有数字 xor 一下,成对的数字 xor 两次等于零。
    vegito2002
        37
    vegito2002  
       2018-02-19 23:10:33 +08:00
    @starqoq 1112222 (N - 1) / 2 = 3, 但是要求的是种类数量, 应该是 2;
    starqoq
        38
    starqoq  
       2018-02-20 16:24:28 +08:00
    @vegito2002
    7
    [1 1] 1 [2 2] [2 2]
    这样不是能凑三双?
    vegito2002
        39
    vegito2002  
       2018-02-20 23:18:02 +08:00
    @starqoq 看楼主 1L 的帖子, 这个例子应该返回 2, 因为只有两**种**.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3785 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 10:21 · PVG 18:21 · LAX 03:21 · JFK 06:21
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.