小学生都能看懂的题解 | #数组中只出现一次的两个数字#

问题描述

假设你有一堆小球，这些小球有不同的编号。现在有人告诉你，这堆小球中有两个编号是特殊的，它们只出现了一次，而其他编号的球都出现了两次。你的任务是找出这两个特殊的编号。

解决方案

我们可以用一种巧妙的方法来找出这两个特殊的编号，这种方法叫作“异或操作”。

方法步骤

1. 计算所有小球编号的异或结果：
1. 从第一个小球开始，用它的编号作为初始值。
2. 对每一个小球的编号进行异或操作，即将新编号和当前的异或结果再做一次异或。
3. 异或操作有一个特性：
1. 任何数和自己异或等于0，任何数和0异或等于自己。
2. 这样，那些出现两次的编号就会相互抵消掉，剩下的就是两个特殊编号的异或结果。
2. 找到特殊编号异或结果中的1：
1. 异或结果是一个数字，它包含了两个特殊编号的信息。
2. 我们需要找到这个结果中任何一个位置上的1。
3. 我们可以用一个简单的技巧来找到这个1的位置：
1. 将异或结果与其负数相与（xorResult & (-xorResult)）。
3. 根据找到的1来区分两个特殊编号：
1. 再次遍历所有小球，这次根据找到的1来区分小球：
1. 如果小球的编号在找到的1的位置上有1，就放到一组。
2. 如果在找到的1的位置上有0，就放到另一组。
3. 对这两组小球分别做异或操作，最终得到的就是那两个特殊编号。

示例代码解释

现在我们用简单的语言来解释一下代码：

public class Solution {
    /**
     * 在整型数组中找出两个只出现一次的数字
     * @param nums 输入的整型数组
     * @return 一个包含两个只出现一次的数字的数组，按非降序排列
     */
    public int[] FindNumsAppearOnce(int[] nums) {
        if (nums == null || nums.length < 2) {
            throw new IllegalArgumentException("Invalid input");
        }

        // 第一步：计算所有数字的异或结果
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num; // 异或操作
        }

        // 第二步：找到异或结果中任意一个为1的比特位
        int mask = xorResult & (-xorResult); // 找到最低位的1

        // 第三步：根据mask区分两个只出现一次的数字
        int num1 = 0, num2 = 0;
        for (int num : nums) {
            if ((num & mask) != 0) { // 如果在mask的位置上有1
                num1 ^= num; // 放入num1组
            } else {
                num2 ^= num; // 否则放入num2组
            }
        }

        // 按非降序排列结果
        if (num1 < num2) {
            return new int[]{num1, num2};
        } else {
            return new int[]{num2, num1};
        }
    }

}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。