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

[kayseen]

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

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

[wolegequ]

跟 py 无关，位运算

[meik2333]

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

[lv2016]

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

[lv2016]

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

[megachweng]

counter?

[icreeper]

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

[megachweng]

```
from collections import Counter

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

>>> 3
```

[xabc]

数据放入集合，完成 😄

集合元素具有唯一性

[mashpolo]

二进制的异或最快

[justfortest]

遍历异或运算就行

[CEBBCAT]

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

[azh7138m]

这不是菜，是蔡

[inhzus]

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

[dangyuluo]

pythonic 的办法是用 set 和 diff

[huntzhan]

蔡得口交

[Nimrod]

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

[20015jjw]

xor

[luclee1996]

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

[luozic]

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

[jmc891205]

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

还有什么讨巧的方法吗？

[robot9]

XOR

[Leigg]

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

[luozic]

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

[luozic]

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

[ebingtel]

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

[wlkq]

使用 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]

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

[bxb100]

^ over

[lshu]

按照我理解的题意
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]

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

[inhzus]

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

当然在楼上我并没有喷

[marsgt]

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

[dovme]

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

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

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

[southsala]

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]

leetcode 里这题目好像还是不是 easy 呢.其实就是位运算.

[dovme]

@southsala #34
public static int getResult(int[] nums){

for (int i = 1;i < nums.length ; i++){
nums[0] ^= nums[i];
}
return result;
}

[dovme]

@dovme #36
public static int getResult(int[] nums){

for (int i = 1;i < nums.length ; i++){
nums[0] ^= nums[i];
}
return nums[0];
}

[Achilless]

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]

....... 我感觉就算不知道 异或，纯数学应该也可以想到吧 sum(set(list)) * 2 - sum(list)

[chefdd]

异或

[zdnyp]

>>> l = [1,2,3,4,1,2,3]
>>> for i in l:
... if l.count(i) == 1:
... print(i)
...
4
>>>
list 没有 count 方法吗？

[exonuclease]

异或一遍

[balaWgc]

leetcode 上有，之前做过，异或遍历可得

[lyc1116]

在数组有序的前提下，复杂度能够优化到 O(logn), 思路是二分查找

[c4f36e5766583218]

这个三角函数我不会！

[brainfxxk]

我觉得这种题真的很无聊...

[harpy]

楼主既然想要做软件开发，还是要继续努力啊，不用位运算，这样的题目也不应该被难住。。可以想象面试官当时的表情。。。