给定一整数数组，其中有p种数出现了奇数次，其他数都出现了偶数次，怎么找到这p个数？

给定一长度为m的整数数组

，其中有p种不为0的数出现了奇数次，其他数都出现了偶数次，找到这p个数。

要求：时间复杂度不大于O(n)，空间复杂度不大于O(1)。

---

        由于时间复杂度不大于O(n)，则不能在遍历数组中嵌套遍历数组。而空间复杂度不大于O(1)，则不能开辟数量上优势或等势于数组长度的内存空间。这需要将数组元素的信息压缩到一个有限的内存空间里，因此需要按位运算。

        按位异或运算⊕是具有如下性质的二元运算：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0，并且满足交换率、结合率。则0是⊕的单位元，即对于任意的二进制数a，都有a⊕0=0⊕a=a。而且a与自身互为逆元，即a⊕a=0。记

        那么，对于任意正整数k，有：

        

        

        对于给定的这个题目，当p=1时，设出现了2k+1次，其余的数都出现偶数次，则根据上述的结论有：

        即将A中所有元素取异或运算即是此问题的解。

        当p=2时，取，则必然b≠0，否则可以推出这两个数相等，从而产生悖论。取，s为c的二进制表示中从后数第一个为1的位数。

        遍历集合A，使每个元素都和c做按位与运算，结果只能是0或者c。取结果为c的元素组成子集A'，由于b的第s位是1，则两个目标数字不会都是A'的元素，否则经过⊕运算，s位的值是0的话，如果b中没有某位是1的数字，则b=0，从而产生矛盾。这样，就将问题转化成了在集合A'中查找只有一种非零整数出现奇数次的问题。即求出为其中的一个解。

        由于，所以

就是另一个解。

        当时，可能不为0，也可能为0。比如，整体取二进制按位异或就是

.所以当时需要对问题进行降阶拆解：

        continuing

原文地址：https://blog.csdn.net/u012632105/article/details/140425282

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！