Single Number：从数组中找出只出现一次的数字

Single Number：从数组中找出只出现一次的数字2015-02-11[ 问题: ]

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory？

翻译：给定一个整数数组，数组中所有元素都出现了两次，只有一个元素只出现了一次，找出这个只出现了一次的元素。

[ 解法: ]

①. 常规解法：时间复杂度为O（n），没能通过

/*** Time Limit Exceeded * 时间复杂度为:O（n），无法通过*/public class Solution1 {public int singleNumber（int[] arr） {int count = 0;for （int i = 0; i < arr.length; i++） {for （int j = 0; j < arr.length; j++） {if （arr[i] == arr[j]） {count++;}}if （count == 1） {return arr[i];} else {count = 0;}}return -1;} public static void main（String[] args） {int[] arr = { 0, 1, 1, 2, 2, 3, 0 };System.out.println（new Solution1（）.singleNumber（arr））;}}

②. 标准解法：使用异或运算

这个程序用了个小技巧：一个整数和它本身异或之后得到值是0，0与其他整数异或得到的是这个整数本身

/*** 利用异或的可交换性*/public class Solution2 {public int singleNumber（int[] arr） {// invalid checkif （arr.length == 0） {return -1;}int result = 0;for （int i = 0; i < arr.length; i++） {result = result ^ arr[i];}return result;} public static void main（String[] args） {int[] arr = { 0, 1, 1, 2, 2, 3, 0 };System.out.println（new Solution2（）.singleNumber（arr））;}}

[ 拓展:]

异或运算的两个法则：

①. a ^ b = b ^ a

②. a ^ b ^ c = a ^ （b ^ c） = （a ^ b） ^ c

真 ^ 假 = 真假 ^ 真 = 真假 ^ 假 = 假真 ^ 真 = 假

/*** 不使用第三个变量,交换两个变量的值*/public class Swap {public static void main（String[] args） {int a = 1, b = 2;System.out.println（"交换前: a = " + a + " , b = " + b）;a = a ^ b;b = a ^ b;a = a ^ b;System.out.println（"交换后: a = " + a + " , b = " + b）;}}

From：csdn博客 zdp072