数组中数字出现的次数

题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

思路

1.这道题要求了时间复杂度和空间复杂度，所以应该用位运算的思路进行求解。
2.既然是在相同中找不同，所以应该和异或操作相关。

• 相同元素异或后，等于0
• 任何元素和0异或后，等于它本身
• a⊕b⊕c⊕b⊕c = a

3.先将数组中的每个元素，相互异或，这样可以得到2个目标元素的异或结果。
4.然后根据异或结果的第一个“1”的位置进行拆分，将原数组分割成两个数组。

• 该位置为1的和该位置不为1的

5.使用两个元素，对两个分割后的数组进行异或操作，就可以得到两个数字了。
6.具体细节可以参看代码中的注释。

Java代码实现

public class Solution {
    public int[] singleNumbers(int[] nums) {
        int firstRes = 0;

        for (int i = 0; i < nums.length; i++) {
            firstRes = firstRes ^ nums[i];
        }

        //firstRes最低位为1的数，例如firstRes = 14(1110),xorNum = 2(0010)
        int xorNum = firstRes & (-firstRes);

        int ans1,ans2;
        ans1 = ans2 = 0;

        for (int i = 0; i < nums.length; i++) {
            //该位置为1
            if((xorNum & nums[i]) == xorNum){
                ans1 = ans1 ^ nums[i];
            }
            //该位置为0
            else{
                ans2 = ans2 ^ nums[i];
            }
        }

        return new int[]{ans1,ans2};
    }
}

Golang代码实现

func singleNumbers(nums []int) []int {
    firstRes := 0

    for i:=0; i<len(nums); i++{
        firstRes = firstRes ^ nums[i]
    }

    xorNum := firstRes & (-firstRes)

    ans1 := 0
    ans2 := 0

    for i:=0; i<len(nums);i++ {
        if (xorNum & nums[i]) == xorNum {
            ans1 = ans1 ^ nums[i]
        }else{
            ans2 = ans2 ^ nums[i]
        }
    }

    return []int{ans1,ans2}
}