前言

今天闲来无事准备刷个算法题，缓解一下办公室尴尬的气氛，放松一下，谁知我竟然跟这题杠上了，我必须得好好研究一下，哈哈

题目

点击进入lintcode，第82题落单的数

给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

举例：

输入：[1,1,2,2,3,4,4]
输出：3
解释：
仅3出现一次，简单点理解就是找出数组中的唯一数

解题思路

先说这题没什么难度，可以利用set的不重复原理，当add 重复的时候会返回false；也可以利用map，如果包含这个key就+1；也可以利用数组排序，然后遍历数组，判断前后2个元素是否相等，如果不相等就返回这个数；然后还可以利用异或运算方法，反正方法有很多，关键是要找出最优算法。

方法一

本方法是循环数组，放入map中，然后把重复的元素的key 的value + 1，然后遍历map，找到key对应value = 1的那个 key就是了

时间复杂度：O(n)
空间复杂度：O(n)

    public static int singleNumber1(int[] A) {int a = 0;Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<A.length;i++){if(map.containsKey(A[i])) {map.put(A[i], map.get(A[i]).intValue()+1);}else {map.put(A[i], new Integer(1));}}Iterator<Integer> iter = map.keySet().iterator();while(iter.hasNext()) {Integer key = iter.next();if(map.get(key) == 1){a = key;}}return a;}

方法二

本方法是对数组进行排序，如果长度=1就直接返回，然后相邻的2个元素进行比较，如果中间数和前一位比不相等，同时和后一位比也不相等，那么这个数就肯定是我们要找的唯一数。

时间复杂度：O(n)
空间复杂度：O(n)

    public static int singleNumber2(int[] A) {int b = 0;Arrays.sort(A);ArrayList<Integer> arr = new ArrayList<Integer>();int n = A.length;//如果只有1位数直接返回if(n == 1){return A[0];}for(int i =0; i < n; i ++){if(i == n-1 && A[i] != A[i - 1]){//当i = 最后一位，如果最后一位和倒数第二位不相等，就返回最后一位b = A[i];}else if(i == 0 && A[i] != A[i + 1]){//当i = 第一位，如果第一位和第二位不相等，就返回第一位b = A[i];break;}else{//当i = 中间位数，如果这个数 不等于前面的数，同时也不等于后面的数，就返回这个数if(i != 0 && i != n-1 && A[i] != A[i - 1] && A[i] != A[i + 1]){b = A[i];}}}return b;}

方法三（异或运算）

先来说说什么是异或运算：
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
利用位移交换的办法，把所有数字异或运算后即可得到只出现一次的数字。
例如：int a [] = {1,1,2,2,3,4,4};
那么1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 4 ^ 4通过位移可以变成
(1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ 3 = 0 ^ 0 ^ 0 ^ 3 = 0 ^ 3 = 3
这个方法也是效率最高的，时间空间复杂度也是最优的

时间复杂度：O(n)
空间复杂度：O(n)

    public static int singleNumber3(int[] A) {int r = A[0];for(int i = 1; i < A.length; i ++){r ^= A[i];}return r;}

本机测试

    public static void main(String[] args) {int a [] = {1,1,2,2,3,4,4,5,6,5,7,6,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25};//int b = StringUtil.singleNumber3(a);long t1 = System.currentTimeMillis();int b1 = StringUtil.singleNumber1(a);long t2 = System.currentTimeMillis();System.out.println("-----方法1耗时（ms）-----" + (t2 - t1) + "----结果---" + b1);long t3 = System.currentTimeMillis();int b2 = StringUtil.singleNumber2(a);long t4 = System.currentTimeMillis();System.out.println("-----方法2耗时（ms）-----" + (t4 - t3) + "----结果---" + b2);long t5 = System.currentTimeMillis();int b3 = StringUtil.singleNumber3(a);long t6 = System.currentTimeMillis();System.out.println("-----方法3耗时（ms）-----" + (t6 - t5) + "----结果---" + b3);}