1. 题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
2.题目分析
- 这题类似于【剑指offer】- 第一个只出现一次的字符位置-33/67
- 我们需要了解一些关于二进制的符号：
一）按位与& 两位全为1，结果才为1 0&0=0；0&1=0；1&0=0；1&1=1 （二）按位或 | 只要有一个为1，结果就为1。 0|0=0； 0|1=1；1|0=1；1|1=1； （三）异或 ^ 两个相应位为“异”（值不同），则该位结果为1，否则为0 0^0=0; 0^1=1; 1^0=1; 1^1=0; 四）取反与运算~ 对一个二进制数按位取反，即将0变为1，1变0 ~1=0 ；~0=1 （五）左移<< 将一个运算对象的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0） 例如： 2<<1 =4 10<<1=100 若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。 例如： 11(1011)<<2= 0010 1100=22 11(00000000 00000000 00000000 1011)整形32bit （六）右移>> 将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。若右移时舍高位不是1（即不是负数），操作数每右移一位，相当于该数除以2。 左补0还是补1得看被移数是正还是负。 例如：4>>2=4/2/2=1 -14（即1111 0010）>>2 =1111 1100=-4 （七）无符号右移运算>>> 各个位向右移指定的位数，右移后左边空出的位用零来填充，移除右边的位被丢弃。 例如：-14>>>2 （即11111111 11111111 11111111 11110010）>>>2 =(00111111 11111111 11111111 11111100)=1073741820
- 还有另外一种做法，将所有的数字进行异或操作，最后得出到的数字，一定是这两个数字进行异或的结果sum，因为两个数字不一样，所以我们得到的sum（二进制）必定有为1的位，我们根据这一位来进行区分；
3. 题目代码
1. hashmap
public static void FindNumsAppearOnce(int[] array, int num1[], int num2[]) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < array.length; i++) { if (map.containsKey(array[i])) { map.remove(array[i]); } else { map.put(array[i], 1); } } for (Integer key : map.keySet()) { System.out.println(key); } boolean f = true; for (Integer key : map.keySet()) { if (f) { num1[0] = key; f = false; } else { num2[0] = key; } } System.out.println(num1[0]); System.out.println(num2[0]); }
2. 二进制
public static int[] singleNumbers(int[] nums) { int sum = nums[0]; for (int i = 1; i < nums.length; i++) { sum = sum ^ nums[i]; } int div = 1; while ((div & sum) == 0) { div = div << 1; System.out.println(div); } int[] a = new int[2]; for (int i = 0; i < nums.length; i++) { if ((div & nums[i]) == 0) { a[0] = a[0] ^ nums[i]; } else { a[1] = a[1] ^ nums[i]; } } return a; }
