V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
kayseen
V2EX  ›  Python

这道 Python 题目有大神会做吗?

  •  
  •   kayseen · 2019-05-09 23:09:22 +08:00 · 5062 次点击
    这是一个创建于 1785 天前的主题,其中的信息可能已经有所发展或是发生改变。
    面试的时候遇到的,搞不懂,题目如下:

    一组数据中只有一个数字出现了一次。其他所有数字都是成对出现的。 请找出这个数字,使用 python 实现
    47 条回复    2019-05-11 00:27:21 +08:00
    wolegequ
        1
    wolegequ  
       2019-05-09 23:11:14 +08:00 via Android   ❤️ 2
    跟 py 无关,位运算
    meik2333
        2
    meik2333  
       2019-05-09 23:12:20 +08:00 via Android
    lv2016
        3
    lv2016  
       2019-05-09 23:14:04 +08:00
    建立一个列表,从第一个数开始搜索,如果在列表里则删除,不在则加入,最后剩的数就是只出现一次的
    lv2016
        4
    lv2016  
       2019-05-09 23:17:27 +08:00
    @lv2016 发现自己菜的真实。。。
    megachweng
        5
    megachweng  
       2019-05-09 23:18:49 +08:00 via iPhone
    counter?
    icreeper
        6
    icreeper  
       2019-05-09 23:23:18 +08:00 via iPhone
    数组里所有数取异或,这题在 leetcode 有
    megachweng
        7
    megachweng  
       2019-05-09 23:26:45 +08:00
    ```
    from collections import Counter

    l = [1, 1, 2, 3, 4, 5, 5, 4]
    c = Counter(l)
    print(c.most_common()[-1][0])

    >>> 3
    ```
    xabc
        8
    xabc  
       2019-05-09 23:37:39 +08:00
    数据放入集合,完成 😄

    集合元素具有唯一性
    mashpolo
        9
    mashpolo  
       2019-05-09 23:43:45 +08:00 via iPhone
    二进制的异或最快
    justfortest
        10
    justfortest  
       2019-05-10 00:29:21 +08:00
    遍历异或运算就行
    CEBBCAT
        11
    CEBBCAT  
       2019-05-10 00:44:23 +08:00 via Android
    不仅菜,还不会搜索…… 上升空间有限啊,加油吧
    azh7138m
        12
    azh7138m  
       2019-05-10 01:25:08 +08:00 via Android   ❤️ 2
    这不是菜,是蔡
    inhzus
        13
    inhzus  
       2019-05-10 01:46:07 +08:00 via Android   ❤️ 1
    reduce(lambda x, y: x ^ y, array)
    dangyuluo
        14
    dangyuluo  
       2019-05-10 02:00:06 +08:00
    pythonic 的办法是用 set 和 diff
    huntzhan
        15
    huntzhan  
       2019-05-10 02:01:41 +08:00   ❤️ 2
    蔡得口交
    Nimrod
        16
    Nimrod  
       2019-05-10 02:41:24 +08:00 via Android
    这种题就是你做一次以后都会做了
    20015jjw
        17
    20015jjw  
       2019-05-10 02:58:05 +08:00 via Android
    xor
    luclee1996
        18
    luclee1996  
       2019-05-10 06:03:13 +08:00 via Android
    luozic
        19
    luozic  
       2019-05-10 07:26:53 +08:00 via iPhone
    python 可以用异或或者位运算,空间复杂度是 O(1 ),不过时间复杂度 O(n)。
    jmc891205
        20
    jmc891205  
       2019-05-10 07:45:32 +08:00
    改下题目:
    一组数据中只有一个数字出现了一次。其他所有数字都是出现了多次的。 请找出这个数字。

    还有什么讨巧的方法吗?
    robot9
        21
    robot9  
       2019-05-10 08:17:45 +08:00
    XOR
    Leigg
        22
    Leigg  
       2019-05-10 08:45:33 +08:00 via iPhone
    @jmc891205 这个用什么讨巧方式,底层都得遍历吧
    reduce/filter/itertools
    luozic
        23
    luozic  
       2019-05-10 08:47:19 +08:00 via iPhone
    搞个树去处理,这种不就是压缩的算法?
    luozic
        24
    luozic  
       2019-05-10 08:47:48 +08:00 via iPhone
    @jmc891205 搞个树去处理,这种不就是压缩的算法核心?
    ebingtel
        25
    ebingtel  
       2019-05-10 09:04:51 +08:00
    @luozic 空间效率 比不过 map 吧?
    wlkq
        26
    wlkq  
       2019-05-10 09:09:29 +08:00
    使用 php 的函数实现了一下。python 也有对应的函数吧

    $a = [1,2,3,4,5,6,7,8,9,10,1,2,3,4,6,7,8,9,10];
    $a_r = array_reverse($a,true);
    $a_f = array_flip($a);
    $a_r_f = array_flip($a_r);

    $result = [];
    foreach ($a_f as $k => $v){

    if($v != $a_r_f[$k]) continue;

    $result[] = $k;
    }

    // 输出 $result : [5]
    anyuhanfei
        27
    anyuhanfei  
       2019-05-10 09:11:20 +08:00
    @jmc891205 用桶排序的一部分方法应该就可以吧,统计出每个元素出现的个数,数量为 1 的就是答案
    bxb100
        28
    bxb100  
       2019-05-10 09:32:21 +08:00 via Android
    ^ over
    lshu
        29
    lshu  
       2019-05-10 09:33:21 +08:00
    按照我理解的题意
    x1+x2+...+xn+x(n+1) = s1
    根据题意 我们令 前 n 个为成对的

    2(x1+x2+...+x(n/2)) + x(n+1) = s1
    同除 2 得到公式 1
    x1+x2+...+x(n/2) + x(n+1)/2 = s1/2

    然后去重求和得到公式 2
    x1+x2+...+x(n/2) + x(n+1) = s2

    两式相减
    结果 = 2*s2 - s1
    程序如下
    l = [1, 1, 2, 2, 7, 4, 5, 5, 4]
    print(2 * sum(set(l)) - sum(l)) == 7
    bengxy
        30
    bengxy  
       2019-05-10 09:42:48 +08:00   ❤️ 1
    为啥大家对新人程序员这么不友好,不都是这么过来的吗?
    只有有几个提出实质解法的,其他都在喷,感情你生下来就会异或运算?
    inhzus
        31
    inhzus  
       2019-05-10 09:47:43 +08:00 via Android
    @bengxy 因为按照楼主的题意直接谷歌都可以搜到上百个答案了 https://i.loli.net/2019/05/10/5cd4d7a7ee817.png

    当然在楼上我并没有喷
    marsgt
        32
    marsgt  
       2019-05-10 10:08:19 +08:00
    贴个 leetcode 中文的链接吧:
    https://leetcode-cn.com/problems/single-number/
    dovme
        33
    dovme  
       2019-05-10 10:16:43 +08:00
    交换律:a ^ b ^ c <=> a ^ c ^ b

    任何数于 0 异或为任何数 0 ^ n => n

    相同的数异或为 0:n ^ n => 0
    southsala
        34
    southsala  
       2019-05-10 10:23:05 +08:00
    Java 实现就这个样子吧,遍历一遍异或运算。
    异或刚好满足这个题目需求,这个题目考点应该就是异或运算。
    两个相同的数比如 88 88,二进制是 1011000 1011000,异或位运算(相同为 0)结果 0000000,也就是 0。

    public static int getResult(int[] nums){
    int result = 0;
    for (int i = 0;i < nums.length ; i++){
    result = result ^ nums[i];
    }
    return result;
    }
    Vegetable
        35
    Vegetable  
       2019-05-10 10:25:55 +08:00
    leetcode 里这题目好像还是不是 easy 呢.其实就是位运算.
    dovme
        36
    dovme  
       2019-05-10 10:33:38 +08:00
    @southsala #34
    public static int getResult(int[] nums){

    for (int i = 1;i < nums.length ; i++){
    nums[0] ^= nums[i];
    }
    return result;
    }
    dovme
        37
    dovme  
       2019-05-10 10:36:26 +08:00
    @dovme #36
    public static int getResult(int[] nums){

    for (int i = 1;i < nums.length ; i++){
    nums[0] ^= nums[i];
    }
    return nums[0];
    }
    Achilless
        38
    Achilless  
       2019-05-10 10:38:29 +08:00
    s = [1, 1, 2, 2, 3, 4, 4]
    for i in s:
    s.remove(i)
    if i in s:
    continue
    else:
    print(i)
    break
    zzzmj
        39
    zzzmj  
       2019-05-10 11:50:48 +08:00
    ....... 我感觉就算不知道 异或,纯数学应该也可以想到吧 sum(set(list)) * 2 - sum(list)
    chefdd
        40
    chefdd  
       2019-05-10 15:48:12 +08:00
    异或
    zdnyp
        41
    zdnyp  
       2019-05-10 15:56:34 +08:00
    >>> l = [1,2,3,4,1,2,3]
    >>> for i in l:
    ... if l.count(i) == 1:
    ... print(i)
    ...
    4
    >>>
    list 没有 count 方法吗?
    exonuclease
        42
    exonuclease  
       2019-05-10 15:57:36 +08:00 via iPhone
    异或一遍
    balaWgc
        43
    balaWgc  
       2019-05-10 16:07:56 +08:00
    leetcode 上有,之前做过,异或遍历可得
    lyc1116
        44
    lyc1116  
       2019-05-10 16:27:47 +08:00
    在数组有序的前提下,复杂度能够优化到 O(logn), 思路是二分查找
    c4f36e5766583218
        45
    c4f36e5766583218  
       2019-05-10 17:54:11 +08:00
    这个三角函数我不会!
    brainfxxk
        46
    brainfxxk  
       2019-05-10 17:57:07 +08:00
    我觉得这种题真的很无聊...
    harpy
        47
    harpy  
       2019-05-11 00:27:21 +08:00
    楼主既然想要做软件开发,还是要继续努力啊,不用位运算,这样的题目也不应该被难住。。可以想象面试官当时的表情。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   999 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 20:01 · PVG 04:01 · LAX 13:01 · JFK 16:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.