找出数组中出现奇数次的数

1. 问题描述

输入： 有一个数组nums[n]，其中有且仅有两个数出现了奇数次，其余的都出现偶数次。
输出： 输出这两个出现奇数次的数。

2. 解决方法

对于只有一个数出现奇数次的数组，我们可以利用异或的性质（同为0异为1），将所有的数相异或，最后就只剩下出现奇数次的数。
但是现在有两个出现了奇数次，要是还按上面的方法，最后的结果将是这两个数的异或结果，我们又分不开。怎么办呢？
我们已经知道了只有一个数出现奇数次的解决方法。能不能考虑一下分治的思想呢，就是将这个数组分成两个子数组，然后保持每一个子数组只有一个奇数次数。可是应该怎么分这两个数组呢，以什么依据来分呢？
假设这两个出现奇数次的数分别为a，b。那么它俩肯定至少有一个bit位是不同的吧，如果全都相同那这俩数就完全相等了。我们如果能找到一个这样的bit位，然后按照这一位是0还是1将这个数组分开，那就得到了上面所说的子数组，每个子数组里仅有一个数出现了奇数次。
详细解释一下：假如a和b的第9位是最低的不相同的位，首先我们要找到这个第九位，令x = a^b，则x的第9位肯定是1，我们用 x & -x得到x的最低位的1，并将其余位都变为0。然后对数组中的元素挨个与这个数（x & -x）相“与”，如果结果为0，说明该数该位上为0，否则说明该数该位上为1，根据结果就可以将其分成两个子数组。首先a和b因为该位上的数字不同一定不在一个组里，其次对于其他的数都出现了偶数次，那么要么全被分到这个子数组要么全被分到那个子数组里，因此每个子数组中其他的数仍然是偶数次。这样问题就完美解决了。

3. 实现

//    数组nums中有且仅有两个元素出现了奇数次
//    返回这两个数public int[] searchOdd(int[] nums){int temp = 0;for (int num: nums) {temp ^= num;}
//        只保留temp的最低位的1temp = temp & -temp;int[] ans = new int[]{0, 0};for (int num: nums) {
//            按照1的位置将数组分为两部分if((temp & num) == temp) ans[0] ^= num;else ans[1] ^= num;}return ans;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！