问题描述
Given a non-empty 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?
Example 1:
Input: [2,2,1] Output: 1 Example 2:
Input: [4,1,2,1,2] Output: 4
解决思路
这题用双层for循环，直接暴力最当然可以，但是题目Note说了，需要linear runtime complexity(时间复杂度为O(n)),且不开辟额外的空间。所以最多只能用单层for循环解决。
这里新知识点：异或运算(^)
- 任何数与0异或，结果都为自身
- 任何数与自身异或，结果都为0
因为数组中，只有一个元素出现一次，其他元素均成双出现，所以将数组内所有元素一起异或运算。除了单一的那个元素，剩下的异或结果为0。0再与单一元素异或，得到这个元素，然后return.
代码
package leetcode;
public class SingleNumber {
public int singleNumber(int[] nums) {
int ret = nums[0];
for (int i = 1; i < nums.length; i++) {
ret ^= nums[i];
}
return ret;
}
}
