题目描述

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?

解法一

思路

这题是用异或求解的经典题目了。首先需要明白异或（^）的几个性质：

  • 顺序无关：多个元素异或的结果与元素的顺序无关。
  • 同一个数异或两次等于没有异或：如4 ^ 3 ^ 4 = 3。
  • 一个数与0异或的结果为其本身：如3 ^ 0 = 3。

明白这些性质了这题就非常容易了，result初始值为0，将数组中每个元素都与result作异或并更新result，最终result的值就是那个唯一只出现一次的元素了。

Python

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

Java

public class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

C++

class Solution {
public:
    int singleNumber(vector<int> &nums) {
        int result = 0;
        for (auto num:nums) {
            result ^= num;
        }
        return result;
    }
};