网站企业备案资料热门网站

一、题目

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

二、思路解析

首先，我们可以先做个小优化：当 nums 数组长度为 2 时，说明这两个元素一定只出现了一次，直接返回即可。

然后就要利用到我们熟悉的两条公式：

x ^ x = 0 

x ^ 0 = x 

由于数组中除了两个数字之外，其他数字都出现了两次，因此我们对数组中的所有数字进行异或运算，得到的结果即为两个只出现一次的数字的异或结果。

在第三部分的代码中，我用 n1 和 n2 表示这两个数。

再对数组使用一次 lowbit 运算，目的是根据最低位的不同，把这两个只出现一次的数字分到两个不同的组。

接着我们在遍历一次数组，当有元素和 lowbit 进行或运算后还不等于零，则他就是 n1 了。

另一个只出现一次的数，就让 n1 和 Double 异或一下就出来了，因为 Double 本身就是这两个数的异或。

三、完整代码

class Solution {public int[] singleNumber(int[] nums) {if(nums.length == 2){return nums;}int Double = 0;for(int i = 0 ; i < nums.length ; i ++){Double ^= nums[i];}int n1 = 0;int lowbit = Double & -Double;for(int j = 0 ; j < nums.length ; j ++){if((nums[j] & lowbit) != 0){n1 ^= nums[j];}  }int n2 = Double ^ n1;return new int[]{n1 , n2};}
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！