数组中出现一次的数

题目描述

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

解题思路一

public static void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
    //因为题目要求除了两个特殊数字只出现一次，其它数字两次，可以用ArrayList快速获取
    ArrayList<Integer> list = new ArrayList<Integer>();
    //遍历array
    for (int i = 0; i < array.length; i++) {
        if (!list.contains(array[i])) { //list不包含当前元素
            list.add(array[i]);
        } else {   //list包含当前元素，即出现第二次，直接删除list中的对应元素
            list.remove((Integer) array[i]);
        }
    }
    //list中肯定只剩两个只出现一次的数字
    num1[0] = list.get(0);
    num2[0] = list.get(1);
}

解题思路二

引用牛客@披萨大叔的思路

链接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811?f=discussion来源：牛客网

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

public static void FindNumsAppearOnce2(int[] array, int num1[], int num2[]) {
    //先排序，相同数字会紧挨在一起
    Arrays.sort(array);
    int index = 0;//遍历下标
    int flag = 1;//记录标志位，判断将特殊数字装进num1还是num2
    while (index < array.length) {
        if (index == 0) {
            //第一位只需和第二位相比
            if (array[index] != array[index + 1]) {
                //不同，则是答案之一
                num1[0] = array[index];
                index++;
            } else {
                //【0】【1】两数相同
                //直接跳到第三个数开始比较
                index += 2;
            }
        } else if (index == array.length - 1) {
            //最后一位只需和前一位比较
            if (array[index] != array[index - 1]) {
                num2[0] = array[index];
            }
            index++;
        } else {
            //当前位需要和前一位和后一位相比
            if (array[index] != array[index - 1] && array[index] != array[index + 1]) {
                switch (flag){
                    case 1: num1[0] = array[index]; flag = 2;break;
                    case 2: num2[0] = array[index];break;
                }
            }
            index ++;
        }
    }
}

public void FindNumsAppearOnce3(int[] array, int[] num1, int[] num2){
    if(array == null || array.length == 1)
        return;//有误
    if(array.length == 2){
        num1[0] = array[0];
        num1[1] = array[1];
        return ;
    }
    int result = 0;
    //所有数异或,得到两个不同值异或的结果，因为相同值异或结果为0
    for (int i = 0; i < array.length; i++) {
        result = result ^ array[i];
    }
    //找出异或结果中二进制位为1的位置
    int index = findFirstOne(result);
    //根据index对所有数进行分组，分成对应index二进制位为1和对应index二进制位为0的数
    for (int i = 0; i < array.length; i++) {
        if(isBit1(array[i], index)){
            num1[0] = num1[0] ^ array[i];
        }else{
            num2[0] = num2[0] ^ array[i];
        }
    }
}

/**
     * 找出当前数二进制位第一个为1的位置
     * @param number
     * @return
     */
public int findFirstOne(int number){
    int index = 0;
    while ((number & 1) == 0 && index < 32){
        index ++;
        number = number >> 1;//右移一位
    }
    return index;
}

/**
     * 判断目标值的index是否为1
     * @param target
     * @param index
     * @return
     */
public boolean isBit1(int target, int index){
    //将target移动index位
    return (target >> index & 1) == 1;
}