给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
public int SingleNumber(int[] nums) { int xor = 0; for(int i = 0;i<nums.Length;i++) { //对同一个元素的两次异或操作等同于+1又-1那样 xor ^= nums[i]; } return xor; }
因为是由0开始,任何数与0的异或都是等于它本身,而任何数与自己异或都是等于0的,所以数据中所有两个相同的数之间的异或都变成0了,最后那个唯一的元素和0异或操作,还是等于它本身就是结果了。