【数组】剑指Offer: 数组中只出现一次的数字

【在线编程】数组中只出现一次的数字

【问题描述】

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

【解题思路 & Java实现】

方法一：先排序，再遍历。时间复杂度O(nlogn).

import java.util.Arrays;

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
//        if (array == null || array.length == 0) {
//            num1[0] =
//        }
        Arrays.sort(array);
        int[] nums = new int[2];

        int i = 0;
        int j = 0;
        while (i < array.length - 1) {
            if (array[i] == array[i + 1]) {
                i = i + 2;
            } else {
                nums[j++] = array[i++];
            }
        }
        if (i == array.length-1) {
            nums[j++] = array[i++];
        }
        num1[0] = nums[0];
        num2[0] = nums[1];

    }

}

方法二：借用 HashMap。时间复杂度 O(n),空间复杂度O(n).

import java.util.HashMap;

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

        HashMap<Integer, Integer> map = new HashMap<>();

        for(int num: array) {
            if(!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num)+1);
            }
        }

        int flag = 0;
        for(int num: array) {
            if(map.get(num) == 1) {
                if(flag == 0) {
                    num1[0] = num;
                    flag = 1;
                } else {
                    num2[0] = num;
                }
            }
        }

    }
}

方法三：使用位运算 ^，相同为0，相异为1.
首先思考一个简单的问题：一个整型数组里只有一个数字只出现一次，其他数字都出现了两次。请找出这个数字。
思路：两个相同的数字异或的结果肯定为0，所以数组中所有元素异或的结果就是那个只出现了一次的数字。

public class Solution {
    public static void main(String[] args) {
        int[] array = {1, 1, 3, 4, 5, 0, 0, 5, 4};
        System.out.println(FindNumsAppearOnce(array));
    }
    public static int FindNumsAppearOnce(int[] array) {
        int xorRes = 0;
        for (int i = 0; i < array.length; i++) {
            xorRes ^= array[i];
        }
        return xorRes;
    }
}

再来思考本题：对数组中所有元素异或的结果肯定就是那两个只出现了一次（单身狗）的数字异或的结果，然后找到异或结果中第一个不为1的位置，按照这个位置是否为1将数组分为两组，这两组中一定分别含有一个单身狗。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        int xorRes = 0; //记录数组中所有元素异或结果，因为有两个出现了一次的数字，所以 xorRes!= 0
        for (int i = 0; i < array.length; i++) {
            xorRes ^= array[i];
        }

        //从右往左找到 xorRes 中第一个为1的位置
        int step = 0; //右移步数，也就是从右往左的位置
        while ((xorRes & 1) == 0 && step < 32) {
            xorRes >>= 1;
            step++;
        }

        //将数组中每个数，按照上面找到的 step 位置是否为1分为两组，这两组一定各包含一个只出现了一次的数字
        for (int i = 0; i < array.length; i++) {
            if (((array[i] >> step) & 1) == 1) {
                num1[0] ^= array[i];
            } else {
                num2[0] ^= array[i];
            }
        }
    }
}