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

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

🏠个人主页：尘觉主页

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

题目链接

牛客网

😊问题描述

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

❤️‍🔥解题思路

1. 利用异或运算：

   • 异或运算的性质是相同的数字异或为 0，0 与任意数字异或的结果为该数字本身。根据这个性质，我们可以对数组中的所有元素进行异或操作。最终得到的结果将是这两个只出现一次的数字的异或结果。
   • 举个例子，对于数组 nums：x ^ x ^ y ^ y ^ z ^ k = 0 ^ 0 ^ z ^ k = z ^ k。

2. 分离这两个数字：

   • 由于 z 和 k 是不同的，z ^ k 的结果必然是一个非零的值。我们需要找到 z 和 k 在二进制表示上的一个不同的位。
   • 我们可以通过 diff = (z ^ k) & -(z ^ k) 来找到 diff，其中 diff 表示 z 和 k 在二进制中最右侧为 1 的位。这个位的存在可以将数组中的数字分为两类，分别与 diff 进行异或运算。

3. 遍历数组分组异或：

   • 再次遍历数组，根据与

     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 最右侧的 1diff &= -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;}
}

复杂度分析

• 时间复杂度：O(n)，需要遍历数组两次。
• 空间复杂度：O(1)，只使用了常量空间来存储结果。

😄总结

通过以上的步骤，我们可以高效地找出数组中只出现一次的两个数字。利用异或运算的特性，我们能够将问题转化为位运算，简化了复杂度。这种思路不仅适用于本题，也为解决类似的问题提供了重要的思路。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞