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

蔚落 2023-09-27 12:07 76阅读 0赞

> **难度等级：中等**

> **上一篇算法：**
> 
> [剑指 Offer 48. 最长不含重复字符的子字符串【字符串】][Offer 48.]

> **力扣此题地址：**
> 
> [剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（Leetcode）][Offer 56 - I. _ - _Leetcode]

### 1.题目：数组中数字出现的次数 ###

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

**示例 1：**

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

### 2.解题思路： ###

> 分两步：
> 
> 1.将数字异或，任何一个数字异或它自己都等于0，而0异或任何数都等于那个数。
> 
> 2.把数组分成两个子数组，使每个子数组包含一个只出现一次的数字，而其他数字成对出现

### 3.代码实现： ###

class Solution {
        public int[] singleNumbers(int[] nums) {
            // 首先先了解下异或运算 ^ ，异或运算也叫做无进位相加，比如 10 ^ 01 = 00。因为1+0=1，这时候当成没有进位，结果就是0。
            // 异或运算满足交换律、结合律。a ^ b = b ^ a   (a ^ b) ^ c = a ^ (b ^ c)
            // 相同的数字异或为0，0与任何数字异或，结果是它本身，所以全体数字异或后，z就等于两个只出现一次的数字异或值
            int z = 0;
            for (int num : nums) {
                z ^= num;
            }
            // 此时z = x ^ y
            // 因为 x和y不相同，所以z中至少有一位为1，否则就为0了。
            // 现在我们寻找这个1。如果有多个1，寻找最低位就行。
            // 这里定义了一个变量m，初始化为1，二进制为(0001)。然后如果最低位和z与运算。结果为0，说明z最低位就为0。
            // m左移一位（乘2）变成2,2的二进制为(0010)。这里判断倒数第二位z和m与运算，等于0吗，等于继续左移，否则就停止。
            int m = 1;
            while ((m & z) == 0) {
                m <<= 1;
            }
            // 此时m的二进制有一位是1，因为x和y不同，这里的不同就体现在了这个1位置上。
            // x和y在这个1位置上肯定有一个是1，另外一个是0。否则都是1或者都是0，那么异或结果不就是0么。
            // 这时候初始化一个x，一个y。x代表这一位上为0的出现一次的数字，y代表这一位上为1的出现一次的数字。
            // 一个数字在这一位要么为0，要么为1。因为二进制嘛。所以其他的数字也会来凑热闹。
            // 但是无妨，因为我们用的是异或，相同的数字出现两次就为0了。（用异或的性质）
            // 比如：nums： 4        1       4       6
            //            0100      0001    0100    0110
            // 我们得到了m为1，也就是(0001)。最低位为0的数字有 4、 4、 6
            // 最低位为1的数字有 0001.
            // x = 4 ^ 4 ^ 6 = 6
            // y = 1
            int x = 0, y = 0;
            for (int num: nums) {
                if ((num & m) == 0) {
                    x ^= num;
                } else {
                    y ^= num;
                }
            }
            return new int[] {x, y};
        }
    }

[Offer 48.]: https://blog.csdn.net/m0_51697147/article/details/127388253
[Offer 56 - I. _ - _Leetcode]: https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/