娱乐 新人的算法挑战 #1

[big_yellow_doge]

新人刚刚从限制会员到新手上路
就看到了@摸鱼奇才咖啡喵发的数学算法挑战,于是就想着自己原创出一个简单的题目来做好了

新人的算法挑战 #1

描述

SS大学里面有许多对情侣,Ta们都是在同一时间进入的SS大学.

总所周知SS大学里面的每一位同学都有一个独一无二的学号(用户id).
比如说big_yellow_doge的学号就是308342.

非常巧的是,这些情侣们的学号中,女生的学号都是偶数,其男朋友的学号是其学号+1.
比如一个女生的学号是520的话,那她男朋友的学号就是521.

现在可怜的单身狗doge不小心混入到了一堆情侣之中.
现在给你这一堆人的学号,请你帮big_yellow_doge找到单身狗doge的学号,以便快速找到doge.

输入

两行
第一行一个整数n,表示这一堆人的数量 2< n <1e6,n=2k+1(k∈Z+)
第二行n个数字 表示SS大学n位同学的学号ai(i=1,2,...,n),2≤ai≤1e9

输出

一行
一个数,表示doge的学号

样例输入

7
10 45 78 44 11 342 79

样例输出

342

样例解释

三组情侣分别是 10与11 78与79 44与45
doge的学号为342

 

因为论坛不支持Markdown和LaTeX，pdf版的题目以及解答可以点 ——>这个链接

答案解析会放在下面的回复里

五月 2, 2022，由big_yellow_doge修改

[旧时叶]

一点思路

剧透

第一反应是sort之后遍历每个奇数位数组位置，如果出现a[i]!=a[i+1]的情况就输出a[i]

 

[旧时叶]

3 分钟前, 旧时叶 说道:

一点思路

  显示隐藏内容

第一反应是sort之后遍历每个奇数位数组位置，如果出现a[i]!=a[i+1]的情况就输出a[i]

 

好吧我没想到（

[big_yellow_doge]

2 分钟前, 旧时叶 说道:

一点思路

  隐藏内容

第一反应是sort之后遍历每个奇数位数组位置，如果出现a[i]!=a[i+1]的情况就输出a[i]

 

思路差不多是可以的呢,不过还有复杂度更低的方法哦,1e6的数据大概率是要TLE的呢

然后判断的应该是a[i]+1 != a[i+1]的时候输出a[i]

还有就是如果doge的学号是最大的值,还会出现数组越界的情况哦

[旧时叶]

刚刚, big_yellow_doge 说道:

思路差不多是可以的呢,不过还有复杂度更低的方法哦,1e6的数据大概率是要TLE的呢

然后判断的应该是a[i]+1 != a[i+1]的时候输出a[i]

还有就是如果doge的学号是最大的值,还会出现数组越界的情况哦

啊这，可以数组开大一点嘛（

不过确实没想到题解的思路，很久没用了（

[big_yellow_doge]

刚刚, 旧时叶 说道:

啊这，可以数组开大一点嘛（

不过确实没想到题解的思路，很久没用了（

确实可以数组开大一点,并且在最后添加一个大于1e9的数 或者直接特判一下这个特殊情况

不过主要的问题还是在于这个数据范围排序 会导致时间上的超限呢输入的数要是在1e5的范围内大概就没有问题了

[big_yellow_doge]

解答参考

剧透

参考代码:

剧透

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, ans = 0, tmp, tmpn;
    cin >> n;
    tmpn = n;
    while(n--)
    {
        cin >> tmp;
        ans = ans^tmp;
    }
    cout << ans^((tmpn>>1)&1) << endl;
}

 

五月 17, 2022，由big_yellow_doge修改

[万人毒]

于 2022/5/2 于 PM6点47分, big_yellow_doge 说道:

思路差不多是可以的呢,不过还有复杂度更低的方法哦,1e6的数据大概率是要TLE的呢

然后判断的应该是a[i]+1 != a[i+1]的时候输出a[i]

还有就是如果doge的学号是最大的值,还会出现数组越界的情况哦

话说 这个可以解决的 比如进行顺序排序 后先判断数组第一位和最后一位 是不是分别等于奇数 ，偶数 如果是的话 情侣规则不匹配了 直接输出 它

然后在继续 

 for (int i = 0; i < (sizeof(a) / sizeof(int)); i=i+2) {
            if (a[i] + 1 != a[i + 1]) {
                std::cout << a[i];
                i = (sizeof(a) / sizeof(int));

            }

        }

#include <iostream>

int main()
{
    
    int a[] = { 88,89,90,98,99};

    if (a[0] % 2 == 1) {



        std::cout << a[0];

    }else if (a[(sizeof(a) / sizeof(int) - 1)] % 2 == 2){




        std::cout << a[(sizeof(a) / sizeof(int) - 1)];


     }else{

        for (int i = 0; i < (sizeof(a) / sizeof(int)); i=i+2) {
            if (a[i] + 1 != a[i + 1]) {
                std::cout << a[i];
                i = (sizeof(a) / sizeof(int));

            }

        }
    }

   

}

虽然有点小问题  

五月 31, 2022，由万人毒修改

[AlGoRiThM]

剧透

目前已知，男同学和女同学学号相邻~，因此，只要从list之中删除不相邻的，即可找到单身狗的学号~

剧透

Sample code:

def main(N, arrays):

    while True:

        select = arrays[0]

        if select+1 in arrays:

            arrays.remove(arrays.index(select+1))

            arrays.remove(0)

        elif select-1 in arrays:

            arrays.remove(arrays.index(select-1))

            arrays.remove(0)

        else:

            return select

没有考虑不存在单身狗的情况~

 

五月 31, 2022，由AlGoRiThM修改

[万人毒]

12 分钟前, AlGoRiThM 说道:

  隐藏内容

目前已知，男同学和女同学学号相邻~，因此，只要从list之中删除不相邻的，即可找到单身狗的学号~

  隐藏内容

Sample code:

def main(N, arrays):

    while True:

        select = arrays[0]

        if select+1 in arrays:

            arrays.remove(arrays.index(select+1))

            arrays.remove(0)

        elif select-1 in arrays:

            arrays.remove(arrays.index(select-1))

            arrays.remove(0)

        else:

            return select

没有考虑不存在单身狗的情况~

 

请考虑一下59 60 61 62 这种情况 像这组就两个单身狗了  60 61 才是情侣 情侣条件 （女 偶数 +1的男才是情侣 情侣女必须比情侣男-1）

[big_yellow_doge]

于 2022/5/31 于 PM9点29分，万人毒说道:

话说 这个可以解决的 比如进行顺序排序 后先判断数组第一位和最后一位 是不是分别等于奇数 ，偶数 如果是的话 情侣规则不匹配了 直接输出 它

然后在继续 

 for (int i = 0; i < (sizeof(a) / sizeof(int)); i=i+2) {
            if (a[i] + 1 != a[i + 1]) {
                std::cout << a[i];
                i = (sizeof(a) / sizeof(int));

            }

        }

#include <iostream>

int main()
{
    
    int a[] = { 88,89,90,98,99};

    if (a[0] % 2 == 1) {



        std::cout << a[0];

    }else if (a[(sizeof(a) / sizeof(int) - 1)] % 2 == 2){




        std::cout << a[(sizeof(a) / sizeof(int) - 1)];


     }else{

        for (int i = 0; i < (sizeof(a) / sizeof(int)); i=i+2) {
            if (a[i] + 1 != a[i + 1]) {
                std::cout << a[i];
                i = (sizeof(a) / sizeof(int));

            }

        }
    }

   

}

虽然有点小问题  

还是前面说的问题，先排序是会TLE的，毕竟排序的复杂度就已经有O(nlog(n))了,不排序则显然会错

[OmegaX]

偶数累加，(奇数-1)*-1后累加，最后结果为负数则*-1+1？

六月 9, 2022，由OmegaX修改

[big_yellow_doge]

10 小时前，OmegaX说道:

偶数累加，(奇数-1)*-1后累加，最后结果为负数则*-1+1？

很妙！是没想到过的O(n)解法

[伽莫夫博士]

第一时间想到的（python）方法是建立一个set存女生一个set存男生，遇到女生直接放进女生set，遇到男生减一然后放入男生set，最后大set减小set

O(1)空间的解法如果在面试时是个很好的follow up问题

六月 27, 2022，由伽莫夫博士修改

[Muriya Tensei]

所有数x 求 (x|1)的异或和，剩下的就是单身狗啦（ 

[playerzhou]

hash表遍历一遍储存所有学号信息，遍历第二遍，当遇到奇数k时查询k-1是否在表里，偶数则查询k+1，若不在表里，则该学号为单身狗

[xdsxly]

编程菜新第一想法map一次遍历

[big_yellow_doge]

于 2022/6/27 于 PM2点27分，伽莫夫博士说道:

第一时间想到的（python）方法是建立一个set存女生一个set存男生，遇到女生直接放进女生set，遇到男生减一然后放入男生set，最后大set减小set

O(1)空间的解法如果在面试时是个很好的follow up问题

set本身插入查找都已经是O(log(n))的复杂度了，在1000000的数据量的情况下是不太对的哦

[big_yellow_doge]

于 2022/6/29 于 AM11点50分，Muriya Tensei说道:

所有数x 求 (x|1)的异或和，剩下的就是单身狗啦（ 

很接近正确答案，有点小问题就是，单身狗的学号是偶数的话，最后的结果会+1导致错误

[big_yellow_doge]

于 2022/6/30 于 AM9点54分，playerzhou说道:

hash表遍历一遍储存所有学号信息，遍历第二遍，当遇到奇数k时查询k-1是否在表里，偶数则查询k+1，若不在表里，则该学号为单身狗

虽然hash表插入和查找都是O(1)，但是感觉实际中速度可能稍微会差那么点意思。这种写法可能要实践一下才能确定是否能在合适时间内出结果了

[big_yellow_doge]

12 小时前，xdsxly说道:

编程菜新第一想法map一次遍历

map的话，不一定是hash实现的，也有可能是红黑树这些，最后的复杂度可能是不一定对的

[伽莫夫博士]

4 小时前，big_yellow_doge说道:

set本身插入查找都已经是O(log(n))的复杂度了，在1000000的数据量的情况下是不太对的哦

python的set相当于cpp的unordered set，复杂度可以保证