题目描述
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
示例:
输入:nums = [4,1,4,6] 输出:[1,6] 或 [6,1]
思路
1.这道题要求了时间复杂度和空间复杂度,所以应该用位运算的思路进行求解。
2.既然是在相同中找不同,所以应该和异或操作相关。
- 相同元素异或后,等于0
- 任何元素和0异或后,等于它本身
- a⊕b⊕c⊕b⊕c = a
3.先将数组中的每个元素,相互异或,这样可以得到2个目标元素的异或结果。
4.然后根据异或结果的第一个“1”的位置进行拆分,将原数组分割成两个数组。
- 该位置为1的和该位置不为1的
5.使用两个元素,对两个分割后的数组进行异或操作,就可以得到两个数字了。
6.具体细节可以参看代码中的注释。
Java代码实现
public class Solution { public int[] singleNumbers(int[] nums) { int firstRes = 0; for (int i = 0; i < nums.length; i++) { firstRes = firstRes ^ nums[i]; } //firstRes最低位为1的数,例如firstRes = 14(1110),xorNum = 2(0010) int xorNum = firstRes & (-firstRes); int ans1,ans2; ans1 = ans2 = 0; for (int i = 0; i < nums.length; i++) { //该位置为1 if((xorNum & nums[i]) == xorNum){ ans1 = ans1 ^ nums[i]; } //该位置为0 else{ ans2 = ans2 ^ nums[i]; } } return new int[]{ans1,ans2}; } }
Golang代码实现
func singleNumbers(nums []int) []int { firstRes := 0 for i:=0; i<len(nums); i++{ firstRes = firstRes ^ nums[i] } xorNum := firstRes & (-firstRes) ans1 := 0 ans2 := 0 for i:=0; i<len(nums);i++ { if (xorNum & nums[i]) == xorNum { ans1 = ans1 ^ nums[i] }else{ ans2 = ans2 ^ nums[i] } } return []int{ans1,ans2} }