1 问题
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
2 分析
第一种方法：我们用位运算
我们想到位运算
（1） a^a=0 （2）a^0=a （2）a^b^c=a^(b^c)=(a^c)^b
1) 对所有运算进行异或运算，最后结果就是两个出现一次的元素异或结果，接下来问题演变成了我们知道两个不同数据的异或值，那么怎么求出这两个值呢？
2) 因为这两个元素不相等，所以异或的结果肯定不是0，也就是可以再异或的结果中找到1位不为0的位，例如异或结果的最后一位为1，我们把这个位置标记为index,然后我们把原始数组分为2个数组，第一个数组中的每个数组的第index位都是1的数组和每个数组的第index位都是0的数组，然后我们再把这个两组数据进行异或处理，分别求出的数据就是我们不同的两个数。
第二种方法：我们用map,key为元素值，如果出现几次放进value里面去，然后最后遍历如果value是1的话，我们得到2个key就行。
3 代码实现
用异或处理的C++版本如下
#include <iostream> #include <vector> using namespace std; void findApperanceTwoNumber(vector<int>& input, int& num1, int& num2) { if (input.size() < 2) { std::cout << "input.size() < 2" << std::endl; return; } int sum = 0; //对所有数据进行异或处理 for (int i = 0; i < input.size(); ++i) { sum ^= input[i]; } //我们通过index找到这个2个不同元素异或值的位1的位置 int index = 0; for (int i = 0; i < 32; ++i) { if (((sum >> i) & 1) == 1) { index = i; break; } } //然后我们遍历数组把每个数据的第index位和1进行异或处理，分别得到结果为1和0的2组数据，然后把这2组数据分别异或处理的和就是2个不同的数据 for (int i = 0; i < input.size(); ++i) { if (((input[i] >> index) & 1) == 1) { num1 ^= input[i]; } else { num2 ^= input[i]; } } } int main() { vector<int> v2; v2.push_back(2); v2.push_back(2); v2.push_back(3); v2.push_back(4); v2.push_back(6); v2.push_back(6); int a = 0, b = 0; findApperanceTwoNumber(v2, a, b); std::cout << "a is "<< a << " b is " << b << std::endl; return 0; }
用map处理的C++版本如下
#include <iostream> #include <vector> #include <map> using namespace std; void findApperanceTwoNumber2(vector<int>& input, int& num1, int& num2) { if (input.size() < 2) { std::cout << "input.size() < 2" << std::endl; return; } map<int, int> datas; for (int i = 0; i < input.size(); ++i) { //C++里面map如果要通过key获取value的话，我们先需要探测map里面是不是有这个key，我们可以count函数,这里如果是java版本的话，就算key不存在的话，我们执行get方法操作，得到的null,没关系。 if (datas.count(input[i])) { if (datas[input[i]] == 1) { //这里用数组形式是因为如果用insert如果发现key一样的话，再次插入会失败，我们所以用数组的形式，这里是通过key更新value datas[input[i]] = 2; } } else { datas[input[i]] = 1; } } ///然后我们再遍历map for (map<int, int>::iterator it = datas.begin(); it != datas.end(); ++it) { if (it->second == 1) { if (num1 == 0) { //这里是获取key num1 = it->first; } else { //这里是获取value num2 = it->first; } } } } int main() { vector<int> v2; v2.push_back(2); v2.push_back(2); v2.push_back(3); v2.push_back(4); v2.push_back(6); v2.push_back(6); int a = 0, b = 0; findApperanceTwoNumber2(v2, a, b); std::cout << "a is "<< a << " b is " << b << std::endl; return 0; }
运行结果如下
a is 3 b is 4
用map处理的java版本如下
import java.io.*; import java.util.ArrayList; import java.util.*; class St { public St() {} ArrayList<Integer> findApperanceTwoNumber2(int[] datas) { ArrayList<Integer> list = new ArrayList<Integer>(); if (datas == null || datas.length < 2) return list; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < datas.length; ++i) { if (map.containsKey(datas[i])) { if (map.get(datas[i]) == 1) { map.put(datas[i], 2); } } else { map.put(datas[i], 1); } } Set<Integer> keys = map.keySet(); for (int key : keys) { if (map.get(key) == 1) { list.add(key); } } return list; } } class test { public static void main (String[] args) throws java.lang.Exception { ArrayList<Integer> list = new ArrayList<Integer>(); St s = new St(); int [] a = {1, 1, 3, 5, 4, 4}; list = s.findApperanceTwoNumber2(a); for (int i : list) { System.out.println("value is " + i); } } }
运行结果如下
value is 3 value is 5
4 总结
如果我们有2个不同数的异或值，那我们怎么知道这2个数据值呢？（这里不是说直接知道这2个元素的数组意思，不然还要你求干吊） 因为这两个元素不相等，所以异或的结果肯定不是0，也就是可以再异或的结果中找到1位不为0的位，例如异或结果的最后一位为1，我们把这个位置标记为index,然后我们把原始数组分为2个数组，第一个数组中的每个数组的第index位都是1的数组和每个数组的第index位都是0的数组，然后我们再把这个两组数据进行异或处理，分别求出的数据就是我们不同的两个数。
C++版本的map操作，我们最好是用数组形式，因为数组形式既可以赋值和可以用来进行修改操作，如果是用insert函数插入的当key是同样而value不是同样值的时候会失败，然后我们获取的话最好也是通过数组形式的key获取，但是获取之前我们需要判断key是否存在map里面的key没有，如果没在的话，直接获取就有问题，但是java的话，就算没有key,获取的也是null值，没关系。
C++的话我们map用count(key)函数来判断是否key存在，而java的话，我么可以用map的containsKey(key)函数判断key是否存在，无论在C++版本还是java版本，我们要对map通过key获取value操作，如果不是通过keySet来获取（就是这个key必然存在map里面的时候），我们都要先用上面的函数进行探测是否包含key,这样代码的健壮性好点。
