原题链接:#136?Single Number
要求:
给定一个整型数组,其中除了一个元素之外,每个元素都出现两次。找出这个元素
注意:算法的时间复杂度应为O(n),最好不使用额外的内存空间
难度:中等
分析:
题目限定了线性的时间复杂度,同时不使用额外的空间,即要求只遍历数组一遍得出结果。由于异或运算 n XOR n = 0, n XOR 0 = n,故将数组中的每个元素进行异或运算即可得到结果
解决方案:
Java - 245ms
class="java" name="code"> public int singleNumber(int[] A) { if(A.length==0) { return 0; } int singleNum = A[0]; for(int i=1; i<A.length; i++) { singleNum = singleNum ^ A[i]; } return singleNum; }
简单测试程序
Python - 93ms
def singleNumber(self, A): singleNum = A[0] for i in range(1,A.__len__()): singleNum = singleNum ^ A[i] return singleNum
简单测试程序