rainyzz's blog

Single Number

###Single Number https://oj.leetcode.com/problems/single-number/
Given an array of integers, every element appears twice except for one. Find that single one.Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

这道题需要的是线性时间并且不需要额外的存储空间,刚开始我以为是不能有自己的中间变量,后来看论坛里讨论的意思是有常量数量的存储空间也可以,即存储空间为O(1),运行时间为O(n)就行了。

刚开始想了几种复杂度比较高的,首先如果存储空间能为O(n),运行时间达到O(n)还是很容易的。

如果存储空间O(1)的话,首先nlog(n)是很容易达到。只要对数组做一下快排nlog(n),然后再扫描一遍,判断每一个数字和后面的数字或前面的数字是否相同,就能找到 Single Number 。

然后要求O(n)就不能排序了,基于比较的排序最低就是nlog(n)了。最后在网上找到了线性的方法。

原链接:http://www.cnblogs.com/changchengxiao/p/3413294.html

主要原理是应用异或来处理。复习一下异或:相同为0,不同为1,同或:相同为1,不同为0。

所以0 xor X = X, X xor X = 0,又由于异或是可交换的,所以将所有的数组元素都异或一下,出现两次的都交换到一起,变成了0,最后剩下的就是 Single Number 。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int singleNumber(int[] A) {
if (A == null || A.length == 0) return 0;
int result = A[0];
for(int i = 1; i < A.length; i++){
result = result ^ A[i];
}
return result;
}
}