面试题56-I.一个数在数组中出现的次数问题一个整型数组nums除了有两个数，其他数出现两次二流。请编写程序找出这两个只出现一次的数字。所需时间复杂度为O(n)，空间复杂度为O(1)。示例1：输入：nums=[4,1,4,6]输出：[1,6]或[6,1]示例2：输入：nums=[1,2,10,4,1,4,3,3]输出：[2,10]or[10,2]限制：2<=nums<=10000解题思路：异或，位运算先说说异或的本质：同一个二进制位是相同为0，否则为1。再说说异或定律：如果两个值相同，则两者异或结果为0，（即任意数与自身异或结果为0）任意数与0的异或结果本身异或或满足交换律、结合律（数学巧合：⊕）交换律：a⊕b=b⊕a结合律：a⊕（b⊕c）=（a⊕b）⊕c回到本题，题目描述，【integerarrayInnums,allbuttwonumbersappeartwice】。然后根据交换结合律，相同的数进行异或，那么相同的数就会变成0，然后根据第二定律，剩下出现过一次的数。这里主要需要实现的是如何保证数组分为两组，使得：只出现一次的数在不同的两组；同一个数组出现在同一个组中。只有这样，每组异或时，最后才会剩下一个数。那么如何分组呢？特别是如何将两个不同的数字分类到不同的组中？具体实现代码如下。代码实现类解决方案：defsingleNumbers(self,nums:List[int])->List[int]:res=0#XORallmembersfornuminnums:res^=num#找到非0位的最低值#&使用位操作div=1while(div&res==0):div<<=1#分组p,q=0,0fornuminnums:ifnum&div:p^=numelse:q^=numreturn[p,q]得到结果以上就是利用异或和位运算的思想求解《面试题56 - I. 数组中数字出现的次数》的主要内容。性质来解决。欢迎关注微信公众号《书所集录》
