数组中只出现一次的数字

1. 题目描述

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

2. 思路

1. 思路一
   • map统计
2. 思路二
   • 对数组中的每个元素相互异或，由于相同的元素异或结果为0，0与任何数异或的结果仍为那个数，因此最后的结果肯定是只出现过一次的那两个数的异或结果
   • 取一个bit为1的数，跟数组中的每个数相与，把数组分成结果不为0和为0的两部分
   • 对这两部分分别异或，就能得出次数为1的不同的两个数

3. 代码

3.1. map统计

• java

public class 数组中只出现一次的数字
{
    public static void main(String[] args)
    {
        new 数组中只出现一次的数字().FindNumsAppearOnce(new int[]{2, 4, 3, 6, 3, 2, 5, 5}, new int[]{0}, new int[]{0});
    }

    public void FindNumsAppearOnce(int[] array, int num1[], int num2[])
    {
        //检查参数
        if (array == null || array.length == 0)
        {
            num1[0] = 0;
            num2[0] = 0;
            return;
        }

        //遍历数组异或，得到的结果必然是两个数异或的结果
        int xorResult = 0;
        for (int val : array)
        {
            xorResult ^= val;
        }
        //根据这个结果取出某一位为1的数bit
        int bit = 1;
        for (int i = 0; i < 32; i++)
        {
            if ((xorResult & bit) != 0)
            {
                break;
            }
            bit <<= 1;
        }
        //遍历数组，跟bit相与，根据结果为0或者非0分成两个子数组
        List<Integer> arrays1 = new LinkedList<>();
        List<Integer> arrays2 = new LinkedList<>();

        for (int val : array)
        {
            if ((val & bit) == 0)
            {
                arrays1.add(val);
            }
            else
            {
                arrays2.add(val);
            }
        }

        //两个子数组分别异或求出结果
        int n1 = 0;
        for (Integer val : arrays1)
        {
            n1 ^= val;
        }

        int n2 = 0;
        for (Integer val : arrays2)
        {
            n2 ^= val;
        }

        num1[0] = n1;
        num2[0] = n2;
    }
}

• go

//时间：O（N）
//空间：O（N）
func FindNumsAppearOnce(nums []int) []int {
	count := make(map[int]int, 0)
	for _, num := range nums {
		count[num]++
	}

	res := make([]int, 0)
	for _, num := range nums {
		if count[num] == 1 {
			res = append(res, num)
		}
	}

	return res
}

3.2. 异或

//时间：O（N）
//空间：O（1）
func FindNumsAppearOnce2(nums []int) []int {
	if len(nums) == 0 {
		return nil
	}

	xorRes := 0
	for _, num := range nums {
		xorRes = xorRes ^ num
	}

	bit := 1
	for i := 0; i < 32; i++ {
		if xorRes&bit != 0 {
			break
		}
		bit = bit << 1
	}

	val1 := 0
	val2 := 0
	for _, num := range nums {
		if num&bit == 0 {
			val1 = val1 ^ num
		} else {
			val2 = val2 ^ num
		}
	}

	res := make([]int, 0)
	res = append(res, val1)
	res = append(res, val2)

	return res
}

4. 参考

• 数组中只出现一次的数字_牛客题霸_牛客网
• 136. 只出现一次的数字 - 力扣（LeetCode）