56-I-数组中数字出现的次数 #

题目描述 #

https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof

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

示例 1：

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

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：

• 2 <= nums.length <= 10000

思路：暴力 #

暴力解法是使用hash表记录次数，再输出次数为1的数组，但是空间复杂度超过了O(1)，不符合题意

思路2：位运算 #

应该是要做运算? 如何降低复杂度到 O(n) 位运算 相同的数异或为0，不同的异或为1，0和任何数异或等于这个数本身

异或就是二进制位相同为0，不同为1

• a^a = 0
• a^0 = a
• a^b^c = a^c^b
• a&(-a) = 最低位为1的二进制(从右往左)

举例 nums = [1,2,10,4,1,4,3,3]

所有异或结果为 2 ^ 10 = 0010 ^ 1010 = 1000 = 8

补码就是取反+1 flag = -8 & 8 = 11......1000 & 00......1000 = 1000 = 8 可分为两组，一组为与 flag 相 与 等于1的 10 ， 另一组为0的[1,2,4,1,4,3,3] 组内异或分别得到【10】和【2】

注意 flag 是找出了最低一位不同的 1，其实其他任意一个不同的1都可以用来判断

参考代码 #

public class Solution {
    public int[] SingleNumbers(int[] nums) {
        int sum = 0;
        //得到异或的结果
        for(int i=0; i<nums.Length; i++){
            sum = sum ^ nums[i];
        }
        //得到sum二进制的1的最低位
        int flag = (-sum) & sum;
        int[] result = new int[2];
        for(int i=0; i<nums.Length; i++){
            if( (flag & nums[i]) == 0){
                result[0]^=nums[i];
            }
            else{
                result[1]^=nums[i];
            }
        }
        return result;
    }
}