数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

解题思路

最简单的就是使用 HashMap，遍历一遍数组，用 map 记录出现的次数，然后再遍历一遍数组，找出出现一次的数字

// num1,num2 分别为长度为 1 的数组。传出参数 // 将 num1[0],num2[0] 设置为返回结果 import java.util.Map; import java.util.HashMap; public class Solution { private Map<Integer, Integer> map = new HashMap<>(); public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { for(int i = 0; i < array.length; i++) { if(!map.containsKey(array[i])) { map.put(array[i], 1); } else { map.put(array[i], map.get(array[i]) + 1); } } for(int i = 0; i < array.length; i++) { if(map.get(array[i]) == 1) { if(num1[0] == 0) { num1[0] = array[i]; } else { num2[0] = array[i]; } } } } }

还可以使用位运算法，首先要了解一下异或运算：

n^0 = nn^n = 0nⁿm = n⁽ⁿm)

我们可以让数组中的每一个数异或一下，最后会得到一个结果，就是两个出现一次的数字的异或结果。我们找出该结果二进制中为 1 的位置 i，因为 1 一定是由 0，1 异或而来，因此要求得两个数中，一定有一个数的二进制中的第 i 个位置为 1， 一个为 0。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

// num1,num2 分别为长度为 1 的数组。传出参数 // 将 num1[0],num2[0] 设置为返回结果 public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { if(array.length == 2) { num1[0] = array[0]; num2[0] = array[1]; } // 用 bitResult 保存每次异或的结果 int bitResult = 0; for(int i = 0; i < array.length; i++) { bitResult ^= array[i]; } // 找出位数为 1 的位置 int index = 0; while((bitResult & 1) != 1) { bitResult >>= 1; index++; } // 将原数组分成两部分，分别包含一个不重复的数字，依据之前的方法再次遍历找出 for(int i = 0; i < array.length; i++) { if(((array[i] >> index) & 1) == 1) { num1[0] ^= array[i]; } else { num2[0] ^= array[i]; } } } }