剑指Offer题解 - Day49

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

力扣题目链接[1]

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

「示例 1：」

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

「限制：」

• 2 <= nums.length <= 10000

思路：

根据题目要求，我们首先得出几个结论：

1. 数组元素都是整型。
2. 只有两个数字出现了一次。
3. 要求时间复杂度是O(n)，空间复杂度是O(1)。

由于要求空间复杂度为O(1)，因此不能使用额外的数据结构存储数组元素的出现次数。

位运算

本题需要使用位运算来题解。位运算不需要开辟额外的空间，可以让空间复杂度降低至O(1) 。

我们要利用 「异或运算」 的一个特性：两个相同数字异或为 0。并且异或运算满足交换律。意味着运算结果与数字顺序无关。

如果说，只有一个数字出现了一次，那么我们可以这样写：

const singleNumber = (nums) => {
 let r = 0;
 for (const num of nums) {
  r ^= num;
 }
 return r;
}

初始化一个结果变量并赋值为 0，因为 0 和任意值异或都等于任意值。然后遍历数组并不断的进行异或运算，最终返回的值就是只出现一次的数字。

但是本题是有两个数字出现了一次，因此不能直接使用此方法进行运算。

假设两个出现一次的数字为x和y。如果说，我们能将 x 和 y 分别放至两个子数组中，并且满足「每个数组只有 x 和 y 出现了一次，其余数字出现两次」。那么就可以直接使用上述方法进行题解。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function(nums) {
    let x = 0; // 初始化结果数字x
    let y = 0; // 初始化结果数字y
    let z = 0; // 初始化x ^ y的结果
    let r = 1; // 初始化获取z首位1的变量
    for (const num of nums) {
        z ^= num; // z最终为x ^ y
    }
    while(!(z & r)) {
        r <<= 1; // r最终为z首位为1的值
    }
    for (const num of nums) {
        if ((num & r) !== 0) x ^= num; // 根据r将x和y拆分到不同子数组中
        else y ^= num;
    }
    return [x, y];
};

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

分析：

首先我们通过遍历数组获取x ^ y的值，记为z。然后我们通过不断左移初始值为1的r，并让r和z执行 「与操作」 。

如果发现z & r 不为0，意味着r找到了x ^ y最右侧值为1的位。那么这个为 1 的位意味着什么？由异或运算的特点可知，异或结果为1，意味着当前位肯定是不同的。也就是说，最终r的值代表了x和y在指定位上值不相同。

那用r来干什么呢？我们可以再一次遍历数组，将数组的元素和r进行 「与运算」 ，由于x和y在指定位上是不同的，因此可以完美的将x和y区分开来。

那么会有人问了，我们将x和y 拆分到两个子数组中，怎么确保子数组中刚好只有x和y只出现一次呢？这是因为数组的每个元素和r进行 「与运算」 ，如果两个数字是相等的，那么指定位上的值肯定是相同的，这样拆分肯定将相同的值拆分到同一个子数组当中。

最极端的情况就是，所有出现两次的数字的指定位都相同，那最终拆分出来的子数组就是一个数组只有x或者y，另一个有剩余所有元素。

这样拆分，就回到文章最初分析的只有一个元素出现一次的情况。接下来只需要将x和y不断和拆分的数组元素 「异或运算」 即可。

最终返回由x和y组成的数组。

总结

本题考查位运算中异或运算的特性。分别分析了一个元素出现一次和两个元素出现一次的情况。在明天的题解中，会继续分析一个元素出现一次，其他元素出现三次的情况，继续学起来吧。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/eubbnm/