题目链接

牛客网

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个数。

解题思路

两个不相等的元素在位级表示上必定至少会有一位存在不同。

将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。

diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。
在所有数中，可以将此位为1和0的数字分成两个部分，再分别进行异或，即可分别得到孤立的两个数。

public class Solution {
   
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
   
        int diff = 0;
        for (int num: array) diff = diff ^ num;
        diff = diff & (-diff);
        for (int num: array) {
   
            if ((num & diff)==0) num1[0] = num1[0]^num;
            else num2[0] = num2[0]^num;
        }
    }
}