【剑指Offer】数组中只出现一次的数字

【题目】

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

【思路】

方法一:

哈希表的方法，时间复杂度是O(n^2)，但是空间复杂度不是O(1)。

方法二:

异或的一个性质是：任何一个数字异或它自己都等于0。

我们从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为0，也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位置，记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。

时间复杂度是O(n^2)，空间复杂度是O(1)。

【代码】

java

方法一：

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

方法二：

//num1,num2分别为长度为1的数组。传出参数 //将num1[0],num2[0]设置为返回结果 import java.util.*; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { int length = array.length; if (length < 2) { return; } // 异或 int tmpOR = 0; for (int a : array) { tmpOR ^= a; } // 找到倒数第一个1出现的位置 int num = 1; while (true) { if ((tmpOR & 1) == 1) { break; } tmpOR >>>= 1; num <<= 1; } // 根据倒数第一个1分为两个子数组 for (int a : array) { if ((a & num) == 0) { num1[0] ^= a; }else{ num2[0] ^= a; } } } }