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

àì夳堔傛蜴生んèń 2023-09-23 21:01 36阅读 0赞

### 前言 ###

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

在前面的文章里介绍了[如何用位运算从一堆数中寻找出现奇数次的1个数？][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`。

![format_png][]

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

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

![format_png 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][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这个特性。

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

作者：Java星辰  
原文链接：https://juejin.cn/post/7182855230889918519

[1]: https://juejin.cn/post/7182054473739534395
[format_png]: https://img-blog.csdnimg.cn/img_convert/fe8e63a72129ab1e21a2df481e25ed4d.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/15776693ff224610265430c5d58f2bae.webp?x-oss-process=image/format,png
[1 1]: https://juejin.cn/post/7182591067856830523