侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

56-Ⅰ数组中数字出现的次数

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 197 阅读 / 1,475 字 / 正在检测是否收录...

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

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

解题思路:

异或的定义:如果两个值相同,异或结果为 $0$,否则为 $1$。

异或有两个重要性质

$$ a ⊕ a = 0 \\ a ⊕ 0 = a \\ $$

因此可以有

$$ \begin{align} &a ⊕ a ⊕ b ⊕ c ⊕ ... ⊕ b ⊕c ⊕x \\ &= 0 ⊕ 0 ⊕ 0 ⊕ x \\ &= x \end{align} $$

回到题目,将数组中相同的数字进行异或,则可以消除掉所有出现两次的数字,最后会只剩下两个只出现一次的数字 $x$ 、$y$ 的异或结果 $xor$。

而 $xor$ 的二进制中为 1 的地方,就是 $x$ 和 $y$ 不同的地方。可以找到 $xor$ 中第一个为 $1$ 的地方,假设为 $bi$。

那么可以将整个数组分为两部分,一部分是 $bi$ 为 $1$ 的数字,一部分是 $bi$ 为 $0$ 的数字。而且这两个只出现一次的数字会分别划分到这两个部分中。

如何快速找到 $xor$ 的二进制中第一个为 $1$ 的地方(从右到左)?

通过 $n$ & $($~$n + 1)$ 这个运算过程,可以得到 $n$ 中第一个 $1$ 的位置。

假设 $n = 101010$,则 $n$ 取反后为 $010101$。此时 $n$ & ~$n = 0$, $~n + 1 = 010110$ ,则 $n$ & $($~$n + 1) = 000010$。

代码:

public int[] singleNumbers(int[] nums) {
    if (nums == null || nums.length == 0 || nums.length % 2 == 1) {
        return new int[0];
    }
    int xor = 0;
    for (int num : nums) {
        xor ^= num;
    }
    int m = xor & (~xor + 1);
    int x = 0, y = 0;
    for (int num : nums) {
        // 分组异或
        if ((num & m) != 0) {
            x ^= num;
        } else {
            y ^= num;
        }
    }
    // 其中没有两个不同的数字
    if (x == 0 && x == y) {
        return new int[0];
    }
    return new int[]{x, y};

复杂度分析

  • 时间复杂度$O(N)$:线性遍历 $nums$ 使用 $O(N)$ 时间。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。
0

评论区