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

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

这是一个创建于 2058 天前的主题，其中的信息可能已经有所发展或是发生改变。

面试的时候遇到的,搞不懂,题目如下:

一组数据中只有一个数字出现了一次。其他所有数字都是成对出现的。请找出这个数字,使用 python 实现

Python

数字

题目

面试

47 条回复 • 2019-05-11 00:27:21 +08:00

wolegequ

2019-05-09 23:11:14 +08:00 via Android

跟 py 无关，位运算

meik2333

2019-05-09 23:12:20 +08:00 via Android

https://www.v2ex.com/t/548708 异或位运算

lv2016

2019-05-09 23:14:04 +08:00

建立一个列表，从第一个数开始搜索，如果在列表里则删除，不在则加入，最后剩的数就是只出现一次的

lv2016

2019-05-09 23:17:27 +08:00

@lv2016 发现自己菜的真实。。。

megachweng

2019-05-09 23:18:49 +08:00 via iPhone

counter?

icreeper

2019-05-09 23:23:18 +08:00 via iPhone

数组里所有数取异或，这题在 leetcode 有

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

2019-05-09 23:37:39 +08:00

数据放入集合，完成 😄

集合元素具有唯一性

mashpolo

2019-05-09 23:43:45 +08:00 via iPhone

二进制的异或最快

justfortest

2019-05-10 00:29:21 +08:00

遍历异或运算就行

CEBBCAT

2019-05-10 00:44:23 +08:00 via Android

不仅菜，还不会搜索…… 上升空间有限啊，加油吧

azh7138m

2019-05-10 01:25:08 +08:00 via Android

这不是菜，是蔡

inhzus

2019-05-10 01:46:07 +08:00 via Android

reduce(lambda x, y: x ^ y, array)

dangyuluo

2019-05-10 02:00:06 +08:00

pythonic 的办法是用 set 和 diff

huntzhan

2019-05-10 02:01:41 +08:00

蔡得口交

Nimrod

2019-05-10 02:41:24 +08:00 via Android

这种题就是你做一次以后都会做了

20015jjw

2019-05-10 02:58:05 +08:00 via Android

xor

luclee1996

2019-05-10 06:03:13 +08:00 via Android

https://leetcode.com/problems/single-number/description/

luozic

2019-05-10 07:26:53 +08:00 via iPhone

python 可以用异或或者位运算，空间复杂度是 O(1 ），不过时间复杂度 O(n)。

jmc891205

2019-05-10 07:45:32 +08:00

改下题目：
一组数据中只有一个数字出现了一次。其他所有数字都是出现了多次的。请找出这个数字。

还有什么讨巧的方法吗？

robot9

2019-05-10 08:17:45 +08:00

XOR

Leigg

2019-05-10 08:45:33 +08:00 via iPhone

@jmc891205 这个用什么讨巧方式，底层都得遍历吧
reduce/filter/itertools

luozic

2019-05-10 08:47:19 +08:00 via iPhone

搞个树去处理，这种不就是压缩的算法？

luozic

2019-05-10 08:47:48 +08:00 via iPhone

@jmc891205 搞个树去处理，这种不就是压缩的算法核心？

ebingtel

2019-05-10 09:04:51 +08:00

@luozic 空间效率比不过 map 吧？

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

2019-05-10 09:11:20 +08:00

@jmc891205 用桶排序的一部分方法应该就可以吧，统计出每个元素出现的个数，数量为 1 的就是答案

bxb100

2019-05-10 09:32:21 +08:00 via Android

^ over

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

2019-05-10 09:42:48 +08:00

为啥大家对新人程序员这么不友好，不都是这么过来的吗？
只有有几个提出实质解法的，其他都在喷，感情你生下来就会异或运算？

inhzus

2019-05-10 09:47:43 +08:00 via Android

@bengxy 因为按照楼主的题意直接谷歌都可以搜到上百个答案了 https://i.loli.net/2019/05/10/5cd4d7a7ee817.png

当然在楼上我并没有喷

marsgt

2019-05-10 10:08:19 +08:00

贴个 leetcode 中文的链接吧：
https://leetcode-cn.com/problems/single-number/

dovme

2019-05-10 10:16:43 +08:00

交换律：a ^ b ^ c <=> a ^ c ^ b

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

相同的数异或为 0：n ^ n => 0

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;
}