Day22_数组中的重复数字_剑指Offer

数组中数字出现的次数

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

示例：

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

限制：

2 <= nums.length <= 10000

解题思路

因为题目要求了时间复杂度不能超过O(n)，空间复杂度不能超过O(1)，所以无法使用HashMap做记录统计值

前置知识：

关于异或（相同返回0，不同返回1）：A^A=0 , A^B=B^A 和 A^0=A ，所以A^B^A = A^A^B = 0^B = B
一个十位数，对应着唯一的二进制值（废话），所以如果两个数的二进制某个位置值不同，那一定是不同值

实现：

对nums中所有数据进行异或，能得到除了重复数字之外的，两个只出现了一次的数的异或结果
找到这个异或结果的一个“1”，因为是不同值，所以异或一定不为0，找到一个异或结果为1的部分，说明两个数在这个位置二进制值一定不同
根据2得到的部位，将nums划分为两个部分分别进行异或，得到的两个值就是目标

Java代码

class Solution {
    public int[] singleNumbers(int[] nums) {
        int ans1 = 0, ans2 = 0, mid = 0, firstDif = 1;
        // 1.找出两个单次出现的数字的异或结果
        for(int num : nums) {
            mid = mid ^ num;
        }
        // 2.找到区分位
        while((mid & firstDif) == 0) {
            firstDif = firstDif << 1;
        }
        // 3.依据区分为去异或
        for(int num : nums) {
            if((num & firstDif) == 0)ans1 = ans1 ^ num;
            else ans2 = ans2 ^ num;
        }
        return new int[]{ans1, ans2};
    }
}

数组中数字出现的次数 II

medium 原题连接：数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例：

输入：nums = [3,4,3,3]
输出：4
输入：nums = [9,1,7,9,7,9,7]
输出：1

提示：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

解题思路

数组中出现三次，说明数字转换成二进制后，每个为1的对应位置在数组中会至少有3个1
将nums的数字全部转换为32位二进制，按对应位填入32位的数组
对该数组每一位都对3取余，只出现一次的会留下一个1
重新拼接数组为十进制数，得到结果

Java代码

class Solution {
    public int singleNumber(int[] nums) {
        // 1.遍历数组，每一位都拆为二进制，按值放入32位数组
        int[] ans = new int[32];
        for(int num : nums) {
            int i=0;
            while(num >0 ) {
                ans[i] += num%2;
                num /= 2;
                i++;
            }
        }
        // 2.对数组每一位都取3的模，获得结果
        for(int i=0; i < ans.length; i++) {
            ans[i] = ans[i]%3;
        }
        // 3.将结果拼为十位数
        int value = 0;
        for(int i=ans.length-1; i>=0; i--) {
            value *= 2;
            value += ans[i];
        }
        return value;
    }
}