剑指 Offer 56 - I. 数组中数字出现的次数

题目描述

一个整型数组nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
输入:nums = [1,2,10,4,1,4,3,3] 输出:[2,10] 或 [10,2]

 🔗题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

思路

本题有很多方法可以解决,但根据题意重复的数字都出现了两次,且本题的空间复杂度要求是O(1),所以使用位运算最为合适。
我们知道两个相同的数异或等于0,任意一个数与0异或等于该数,即,若数组中只有一个只出现一次的数字,其它数字都出现了两次,就可以使用异或运算得到只出现一次的数字,但本题有所不同,有两个只出现一次的数字,使用异或得到的是两数异或的结果,但我们可以从该结果入手,两数只出现一次且不同,则它们的二进制形式至少有一位是不同的,因此可以根据该二进制位将数组分为分别包含这两数的子数组,遍历异或即可分别提取出子数组中的结果数。
如数组[4,1,6,4],遍历异或得到 0001 异或 0110 = 0111,取出最低位的1为0001,
则根据该位将数组分为(x & 0001)== 0和(x & 0001)== 1的两组,即[4,6,4]和[1],
分别再进行异或即可得到子数组的结果值

代码实现

class Solution {
    public int[] singleNumbers(int[] nums) {
        int m = 0;
        int x1 = 0;
        int x2 = 0;
        for(int num : nums){ //两个只出现一次的数字的异或结果
            m ^= num;
        }
        int n = m & (-m); //m最低位的1
        for(int num : nums){ //分组异或
            if((num & n) != 0){
                x1 ^= num;
            }else{
                x2 ^= num;
            }
        }
        return new int[]{x1, x2};
    }
}

剑指 Offer 56 - II. 数组中数字出现的次数 II

题目描述

在一个数组nums中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
输入:nums = [9,1,7,9,7,9,7] 输出:1
🔗题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

思路


代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        //记录所有数字各二进制位的1的出现次数
        for(int num : nums){
            for(int j = 0; j < 32; j++){
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        //通过左移操作和或运算,将counts数组中各二进位的值恢复到数字res上
        int res = 0;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % 3;
        }
        return res;
    }
}