【试题***】找出落单的数/数组中只出现一次的数
数组中只出现一次的数字
https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
找出落单的数/数组中只出现一次的数
题目:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解题思想:
异或的特性:0^任意数=任意数,任意数^任意数=0;异或计算的无序性(即1^2^3 = 2^3^1)
1.对原数组所有的数异或得到两个不重复数的异或结果
2.根据两个不重复数的异或结果的二进制位的差异,将原数组分为两组(每组中有一个不重复数)
如:两个数如果分别是 6 和 7
0000 * * * 00 0110
0000 * * * 00 0111
根据原数组中所有数的二进制位最后一位是0或1,将原数组分为两组。
3.再分别对两组数异或
//num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.ArrayList; import java.util.Scanner; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int x = 0; for(int i = 0; i < array.length; i++){ x ^= array[i]; } int index = findBitRight1Index(x); int res1 = 0, res2 = 0; for(int i = 0; i < array.length; i++){ int temp = array[i]; if( ((temp >> index) & 1) == 0 ){ res1 ^= temp; } else{ res2 ^= temp; } } num1[0] = res1; num2[0] = res2; } // 两个数异或结果,从右向左找到差异位,将原来的数组分为两组 public int findBitRight1Index(int number){ int index = 0; while( (number & 1) == 0 && index < 32){ number >>= (++index); } return index; } }