leetcode136~Single Number

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) 空间复杂度O(1) 这种题目，想到方法就很简单，想不到就直接蹦~

使用异或。两个相同的数异或得到0，这样，数组中每个数都异或一次，最后剩下的那个数肯定是只出现一次的数。 交换律：A XOR B = B XOR A 结合律: A XOR B XOR C = A XOR (B XOR C) = (A XOR B) XOR C 自反性： A XOR B XOR B = A XOR 0 = A

public class SingleNumber { public int singleNumber(int[] nums) { if(nums==null || nums.length==0) return 0; int res = 0; for(int i=0;i<nums.length;i++) { res = res^nums[i]; } return res; } }