算法的学习笔记—数组中只出现一次的数字(牛客JZ56)

在这里插入图片描述

😀前言
在数组中寻找只出现一次的两个数字是一道经典的问题，通常可以通过位运算来有效解决。本文将详细介绍这一问题的解法，深入解析其背后的思路。

🏠个人主页：尘觉主页

文章目录

🥰数组中只出现一次的数字
- 题目链接
- 😊问题描述
- ❤️‍🔥解题思路
- 😀Java 实现
- - 复杂度分析
- 😄总结

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

题目链接

牛客网

😊问题描述

给定一个整型数组，其中除了两个数字以外，其他数字均出现两次，目标是找出这两个只出现一次的数字。以数组 nums 为例：[x, x, y, y, z, k]，其中 x、y 出现两次，而 z 和 k 各自只出现一次。

❤️‍🔥解题思路

利用异或运算：
- 异或运算的性质是相同的数字异或为 0，0 与任意数字异或的结果为该数字本身。根据这个性质，我们可以对数组中的所有元素进行异或操作。最终得到的结果将是这两个只出现一次的数字的异或结果。
- 举个例子，对于数组 nums：x ^ x ^ y ^ y ^ z ^ k = 0 ^ 0 ^ z ^ k = z ^ k。
分离这两个数字：
- 由于 z 和 k 是不同的，z ^ k 的结果必然是一个非零的值。我们需要找到 z 和 k 在二进制表示上的一个不同的位。
- 我们可以通过 diff = (z ^ k) & -(z ^ k) 来找到 diff，其中 diff 表示 z 和 k 在二进制中最右侧为 1 的位。这个位的存在可以将数组中的数字分为两类，分别与 diff 进行异或运算。
遍历数组分组异或：
- 再次遍历数组，根据与
```
diff
```
  的异或结果将数字分为两组：
  - 如果 num & diff == 0，则将 num 与第一个结果变量（如 res[0]）进行异或。
  - 否则，将 num 与第二个结果变量（如 res[1]）进行异或。
- 最终，res[0] 和 res[1] 就是我们要找的两个数字。

😀Java 实现

以下是用 Java 语言实现的完整代码：

public class Solution {
    public int[] FindNumsAppearOnce(int[] nums) {
        int[] res = new int[2];
        int diff = 0;

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

        // 第二步：获取 diff 最右侧的 1
        diff &= -diff;

        // 第三步：分组异或
        for (int num : nums) {
            if ((num & diff) == 0) {
                res[0] ^= num;  // 与 diff 的结果为 0 的数
            } else {
                res[1] ^= num;  // 与 diff 的结果不为 0 的数
            }
        }

        // 可选步骤：为了返回时更有序，可以选择排序
        if (res[0] > res[1]) {
            swap(res);
        }
        return res;
    }

    private void swap(int[] nums) {
        int t = nums[0];
        nums[0] = nums[1];
        nums[1] = t;
    }
}