Python实现数组中只出现一次的数字

作者: Gxxx_xx | 来源:发表于2018-05-26 22:02 被阅读0次

Python实现数组中只出现一次的数字
面试题56_2：数组中唯一只出现一次的数字
面试题56(1):数组中数字出现的次数
【不熟练】知识迁移能力-数组中只出现一次的数字
JZ-040-数组中只出现一次的数字
面试题56 - II. 数组中数字出现的次数 II
Leetcode高频算法思路——起步
《剑指offer第二版》面试题56 题目二：数组中唯一只出现一次
剑指offer | 数组中只出现一次的数字
面试题56 - II. 数组中数字出现的次数 II

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

答案简直神了，完全没往二进制上去想，更笨的是见到题目就觉得，明明有一百种笨方法来解决啊，不知道考点在哪里。。==答案太巧妙，只用遍历三次数组。以此记录一下：

任何一个数字异或他自己都等于0，0异或任何一个数都等于那个数。数组中出了两个数字之外，其他数字都出现两次，那么我们从头到尾依次异或数组中的每个数，那么出现两次的数字都在整个过程中被抵消掉，那两个不同的数字异或的值不为0，也就是说这两个数的异或值中至少某一位为1。我们找到结果数字中最右边为1的那一位i，然后一次遍历数组中的数字，如果数字的第i位为1，则数字分到第一组，数字的第i位不为1，则数字分到第二组。这样任何两个相同的数字就分到了一组，而两个不同的数字在第i位必然一个为1一个不为1而分到不同的组，然后再对两个组依次进行异或操作，最后每一组得到的结果对应的就是两个只出现一次的数字。