题解 | #数组中只出现一次的两个数字#
数组中只出现一次的两个数字
https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ public int[] FindNumsAppearOnce (int[] nums) { //遍历数组,进行异或运算 int tmp = 0; for(int num : nums){ tmp ^= num; } //找分组进行与运算的那个值 int mark = 1; while((mark & tmp) == 0){ mark = mark << 1; } //进行分组 int a = 0,b = 0; for(int num : nums){ if((mark & num) == 0){ a ^= num; }else{ b ^= num; } } if(a < b){ return new int[]{a,b}; } return new int[]{b,a}; } }
异或:也叫半加,相当于不带进位的二进制算法。两值不同,结果为1;两值相同为0,任何数与0异或都为原值。
解题思路:
- 先对数组里面的数进行遍历进行异或运算,可达到最终两个数的异或结果tmp = a⊕b
- 对原数组进行分组,例如[a,c,c],[b,d,d]。如何确定分组条件是关键。
- 对tmp与mark=1进行异或,从低位开始,直到找到某位为1,此时mark作为分组条件