题解 | #数组中只出现一次的两个数字#
数组中只出现一次的两个数字
https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8
解题思路:
- step 1:遍历整个数组,将每个元素逐个异或运算,得到a⊕b。
# 这个是完全能够理解的,两个数一样的异或,变成0。
- step 2:我们可以考虑位运算的性质,找到二进制中第一个不相同的位,将所有数组划分成两组。
# 这里为什么是找到1,是因为1的数据,表示之前a和b异或运算的不同位,才有1的结果,所以是对k&target,求位 k << = 1
# 这里经过实例后,可以得到结果。
- step 3:遍历数组对分开的数组单独作异或连算。
# 这里还是依旧要做异或运算的,跟之前没有区别,只是通过k值 &区分了,两个不同的数。
# 0 异或 上一个数,得到的就是,那个数!!
- step 4:最后整理次序输出。
实例演示:
可以用[1,4,1,6],演示就知道了
- step 1:遍历整个数组,将每个元素逐个异或运算,得到a⊕b。
[001, 100, 001, 110] ,异或运算后得到 target = 010,也就是2
- step 2:我们可以考虑位运算的性质,找到二进制中第一个不相同的位,将所有数组划分成两组。
k = 1,通过k找出,a和b不同的位,因为之前异或运算剩下的值,就是不同的位,k= 010,也就是2
- step 3:遍历数组对分开的数组单独作异或连算。
- step4:最后整理次序输出。
(k & num[i] == 0) 区分不同数, a ^= num[i],去掉相同的数。
return a<b?new int[]{a,b}:new int[]{b,a};
总之在于理解关键点:
过滤掉相同数:异或 a⊕b,
找出不同数: 异或后,找出不同位,
在通过 与不同位,区分两个数,再异或得结果。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ public int[] FindNumsAppearOnce (int[] nums) { int target = 0; for(int i=0; i<nums.length; i++) { target ^= nums[i]; } int k = 1; while((k&target) == 0) { k <<= 1; } int a = 0, b = 0; for(int i=0; i<nums.length; i++) { if((k & nums[i]) ==0) { a ^= nums[i]; } else { b ^= nums[i]; } } return a<b?new int[]{a,b}:new int[]{b,a}; } }