算法 | 如何用位运算从一堆数中寻找出现奇数次的2个数？

前言

本文主要介绍如何用位运算从一堆数中寻找出现奇数次的2个数，在一个数组中有很多元素，其中只有a，b两种元素出现了奇数次，其他的数都出现了偶数次，那么如何用把这两个数给寻找出来呢？

在前面的文章里介绍了如何用位运算从一堆数中寻找出现奇数次的1个数？，一个是找出1个数，一个是找出2个数，虽然只有增加了1个数，但是难度却增加了好几倍。

思路解析

得到a ^ b

假如有一组数，arr = [a, a, a, b, b, b, c, c, c, c, d, d, d, d]，其中只有a和b出现了奇数次，其他的数都出现了偶数次，那我们的目的就是把a和b给找出来。

在寻找一个数的时候，我们使用的是把数组中所有元素都进行异或一遍就能得到结果。

那么现在对arr数组异或会得到什么呢？会得到一个a ^ b，那么现在的问题就是，如何把得到的结果a ^ b给分开，那么如何把把这1个数拆成2个数呢？或者如何根据这个数，再从数组里找到a和b呢？

根据a ^ b分组

如果说，能把数组分为两组，而a和b刚好能够分别被分到两个组中，是不是就好判断了？

接下来就来看下如何对数组进行分组。

a ^ b这个数不相等，那么这个数肯定是不为0的，那么这个数的二进制肯定有一个位值为1。

假如a ^ b对应的二进制为00100101100，以最右侧1为例，这个1要么属于a，要么属于b。例如下图中，第2位置为1。

把范围扩大一下，在整个数组中，每个数的二进制的第2位置，要么为1要么为0。

此时，就把数组分为了两组，一组为第2位置为1的，另一组为第2位置为0的，假设a二进制的第2位置为1，如图。

分离a、b

既然把a和b这两个元素给分到了两组，那么只需要对其中一组的每个元素进行异或就能到的一个值了，例如把二进制的第2个位置为1的这一组所有元素进行异或，就能把a给取出来。

既然把a取出来了，那b呢？再把另一组进行异或一遍？不不不，把a和a ^ b进行异或一下不就得到b了吗？

整体思路

总结下取出a和b的过程：

1. 先对数组arr所有元素进行异或操作，得到a ^ b。
2. 根据a ^ b的二进制最右侧1位置，把数组分为两组。
3. 对其中一组(例如含有a的)的所有元素进行异或操作，分离出a。
4. 再与a ^ b进行异或，分离出b。

关于如何找到一个数二进制最右侧的1，可以参考之前的一篇文章。

如何找到一个数二进制最右侧的1

代码实现

接下来看下代码是如何实现的。

public class Code17_FindOddTwo {
    public static void findOddTwo(int[] arr) {
        int tmp = 0;
        for (int i = 0; i < arr.length; i++) {
            tmp ^= arr[i];
        }
        // 保留最右侧的1
        int rightOne = tmp & (-tmp);
        int resA = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) !=0) {
                resA ^= arr[i];
            }
        }
        int resB = tmp ^ resA;
        System.out.println(resA);
        System.out.println(resB);
    }
    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4};
        findOddTwo(arr);
    }
}

执行一下，看下输出结果：

1
2

可以看到，确实把数组中只出现了奇数次的1 和 2给打印出来了。

总结

本文主要介绍如何用位运算从一堆数中寻找出现奇数次的2个数，在实现过程中，利用了异或和二进制最右侧的1这个特性。

当然实现方法有很多种，如果你有更好的办法，欢迎在评论区留言交流。