本文共 1938 字，大约阅读时间需要 6 分钟。

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

解法1：

重新申请一个列表s=[]，遍历这个数组：

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        s = []        for num in nums:            if num not in s:                s.append(num)            else:                s.remove(num)        return s[0]

解法2：

使用python的异或操作，0异或任何数不变，任何数与自己异或为0。a⊕b⊕a=b。异或满足加法结合律和交换律。

class Solution(object):    def singleNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        a = 0        for num in nums:            a = a ^ num        return a

以下是Java版本：

题目意思是一个数组中，只有一个元素是唯一的，其他元素都是两次出现的。

题解：这道题运用位运算的异或。异或是相同为0，不同为1。所以对所有数进行异或，得出的那个数就是single number。初始时先让一个数与0异或，然后再对剩下读数挨个进行异或。

这里运用到异或的性质：对于任何数x，都有x^x=0，x^0=x

1     public int singleNumber(int[] A) {2         int result = 0;3         for(int i = 0; i

同时异或还有性质：

 交换律 A XOR B = B XOR A

 结合律 A XOR B XOR C = A XOR (B XOR C) = (A XOR B) XOR C

 自反性 A XOR B XOR B = A XOR 0 = A

所以对于这个数组来说，因为只有一个数字是single的，所以数组可以表示为 a a b b c c d d e。 那么利用上述规律可以异或结果为 0 0 0 0 e。这样写的代码为：

1 public static int singleNumber(int[] A) {2     for (int i = 1; i < A.length; i++) {3         A[i] ^= A[i-1];4     }5     return A[A.length-1];6 }

方法是使用异或运算。

0 ^ x = x   x ^ x = 0

首先设val = 0，最后返回 val 。 其中 val = val ^ a1 ^ a2 ... ^ an。 由于其中两两相同的在异或中已经为0了，所以最后结果就是那个唯一的数。

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

Test

1.	public static void main(String[] args){  2.	    int[] numbers = {7, 2, 3, 4, 7, 3, 4};  3.	    int b = new Solution().singleNumber(numbers);  4.	    System.out.println(b);  5.	      6.	}

转载地址：http://ssuvi.baihongyu.com/