深圳网站建设案,软件开发需要用什么软件,cloudfare wordpress,科技加盟网站建设#x1f600;前言 在数组中寻找只出现一次的两个数字是一道经典的问题#xff0c;通常可以通过位运算来有效解决。本文将详细介绍这一问题的解法#xff0c;深入解析其背后的思路。 #x1f3e0;个人主页#xff1a;尘觉主页 文章目录 #x1f970;数组中只出现一次的数字… 前言 在数组中寻找只出现一次的两个数字是一道经典的问题通常可以通过位运算来有效解决。本文将详细介绍这一问题的解法深入解析其背后的思路。 个人主页尘觉主页 文章目录 数组中只出现一次的数字题目链接问题描述❤️解题思路Java 实现复杂度分析 总结 数组中只出现一次的数字
题目链接
牛客网
问题描述
给定一个整型数组其中除了两个数字以外其他数字均出现两次目标是找出这两个只出现一次的数字。以数组 nums 为例[x, x, y, y, z, k]其中 x、y 出现两次而 z 和 k 各自只出现一次。
❤️解题思路 利用异或运算 异或运算的性质是相同的数字异或为 00 与任意数字异或的结果为该数字本身。根据这个性质我们可以对数组中的所有元素进行异或操作。最终得到的结果将是这两个只出现一次的数字的异或结果。举个例子对于数组 numsx ^ 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 最右侧的 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连支持一下创造不易您们的支持是我的动力
