剑指Offer系列（java版，详细解析）56.数字中数字出现的次数

心已赠人 2023-01-13 10:21 81阅读 0赞

# 题目一 #

## 题目描述 ##

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

难度中等371收藏分享切换为英文接收动态反馈

一个整型数组 `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`

## 测试用例 ##

功能测试（数组中有多对重复的数字；数组中没有重复的数字）

## 解题思路 ##

注意一次和两个这种量词，我们需要想到异或运算的一个性质：**任何一个数字异或它自己都等于0。**

1.  从头到尾异或数中的每个数字，得到两个只出现一次的数字的异或结果
2.  从1结果数字找到第一个为1的位的位置，记为n
3.  遍历数组，根据n位是否为1分别两组，从头到尾异或，则两组异或之后的数字即为只出现一次的两个数字。

## 自己解题 ##

一脸懵逼

## 参考解题 ##

class Solution {
        public int[] singleNumbers(int[] nums) {
            int x = 0, y = 0, n = 0, m = 1;
            for(int num : nums)               // 1. 遍历异或
                n ^= num;
            while((n & m) == 0)               // 2. 循环左移，计算 m
                m <<= 1;
            for(int num: nums) {              // 3. 遍历 nums 分组
                if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
                else y ^= num;                // 4. 当 num & m == 0
            }
            return new int[] {x, y};          // 5. 返回出现一次的数字
        }
    }

# 题目二 #

## 题目描述 ##

数组中唯一只出现一次的数字

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

## 测试用例 ##

功能测试（唯一值出现一次的数字分别为0、正数、负数；重复出现三次的数字分别是0、正数、负数）

## 解题思路 ##

还是位运算解决思路。

如果一个数字出现三次，那么它的二进制表现表示的每一位也出现三次。如果把所有出现三次的数字的二进制表示的每一位都加起来，那么每一位的和都能被3整除，不能被3整除的其余数就是只出现一次的数字在该为的值。

时间复杂度为O(n)  
空间复杂度为O(1)

## 参考解题 ##

class Solution:
        def singleNumber(self, nums: List[int]) -> int:
            counts = [0] * 32
            for num in nums:
                for j in range(32):
                    counts[j] += num & 1
                    num >>= 1
            res, m = 0, 3
            for i in range(32):
                res <<= 1
                res |= counts[31 - i] % m
            return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)

# 题目考点 #

*  考察应聘者的知识迁移能力。
 *  考察应聘者对二进制和位运算的理解。

[Offer 56 - I.]: https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/