首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python 学习手册
Python Cookbook
Python 基础教程
Python Sites
PyPI - Python Package Index
http://www.simple-is-better.com/
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
V2EX  ›  Python

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

  •  
  •   kayseen · 46 天前 · 3709 次点击
    这是一个创建于 46 天前的主题,其中的信息可能已经有所发展或是发生改变。
    面试的时候遇到的,搞不懂,题目如下:

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

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

    >>> 3
    ```
        8
    xabc   46 天前
    数据放入集合,完成 😄

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

    还有什么讨巧的方法吗?
        21
    robot9   46 天前
    XOR
        22
    Leigg   46 天前 via iPhone
    @jmc891205 这个用什么讨巧方式,底层都得遍历吧
    reduce/filter/itertools
        23
    luozic   46 天前 via iPhone
    搞个树去处理,这种不就是压缩的算法?
        24
    luozic   46 天前 via iPhone
    @jmc891205 搞个树去处理,这种不就是压缩的算法核心?
        25
    ebingtel   46 天前
    @luozic 空间效率 比不过 map 吧?
        26
    wlkq   46 天前
    使用 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]
        27
    anyuhanfei   46 天前
    @jmc891205 用桶排序的一部分方法应该就可以吧,统计出每个元素出现的个数,数量为 1 的就是答案
        28
    bxb100   46 天前 via Android
    ^ over
        29
    lshu   46 天前
    按照我理解的题意
    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
        30
    bengxy   46 天前   ♥ 1
    为啥大家对新人程序员这么不友好,不都是这么过来的吗?
    只有有几个提出实质解法的,其他都在喷,感情你生下来就会异或运算?
        31
    inhzus   46 天前 via Android
    @bengxy 因为按照楼主的题意直接谷歌都可以搜到上百个答案了 https://i.loli.net/2019/05/10/5cd4d7a7ee817.png

    当然在楼上我并没有喷
        32
    marsgt   46 天前
    贴个 leetcode 中文的链接吧:
    https://leetcode-cn.com/problems/single-number/
        33
    dovme   46 天前
    交换律:a ^ b ^ c <=> a ^ c ^ b

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

    相同的数异或为 0:n ^ n => 0
        34
    southsala   46 天前
    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;
    }
        35
    Vegetable   46 天前
    leetcode 里这题目好像还是不是 easy 呢.其实就是位运算.
        36
    dovme   46 天前
    @southsala #34
    public static int getResult(int[] nums){

    for (int i = 1;i < nums.length ; i++){
    nums[0] ^= nums[i];
    }
    return result;
    }
        37
    dovme   46 天前
    @dovme #36
    public static int getResult(int[] nums){

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