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?

题目意思:找出一个数组中的一个不同的元素。

新手想法,先排序,然后循环找出那个前后不一样的那一个。(题目给出意思是不能运用其他数组去标记的,否则,利用一个容器去记录的话,那复杂度肯定是N的)

高手想法,利用异或的位运算。

只要任意两个相同的数异或之后都是0,那么只要把所有的元素都异或在一起,那么最后剩下的值就是没有相同的数和它一起变成0了。

public class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i=0;i<nums.length;i++)
result ^= nums[i];
return result;
}
}
05-07 15:32