剑指offer-41-数组中只出现一次的数字

思路

• Set<integer> 集合</integer>
• 异或运算,异或有交换律，异或的结果是两个不同的数异或得到，通过这个数的二进制中某个1，对整个数组进行分组。分组之后可以转换为求一个数组中只有一个数字是1位的场景。

代码

Set集合

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.*;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        Set<Integer> arr=new HashSet<>();
        for(int i=0;i<array.length;i++){
            if(!arr.contains(array[i])){
              arr.add(array[i]);    
            }else{
              arr.remove(array[i]);
            }
        }
        int p=0;
        for(Integer i:arr){
            if(p==0){
                num1[0]=i;
                p++;
            }else{
                num2[0]=i;
            }
        }
    }
}

异或运算

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int res=0;
        for(int i=0;i<array.length;i++){
            res=res^array[i];
        }
        int p=0;
        while((res&1)!=1){
            res=res>>1;
            p++;
        }
        int res1=0,res2=0;
        for(int i=0;i<array.length;i++){
            if(((array[i]>>p)&1)==1){
                res1=res1^array[i];
            }else{
                res2=res2^array[i];
            }
        }
        num1[0]=res1;
        num2[0]=res2;
    }
}