LeetCode—— 只出现一次的数字

题目描述

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

说明：

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

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

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

一、CPP

1. 异或法（位操作）：

解题思路:此题最好的思路就是下面的这种异或做法。因为数组中的所有元素除了一个出现一次的，其余都出现两次。把整个数组的元素当作异或的对象，根据异或的性质，出现两次的在整个数组元素异或之后必定相互抵消（为0），而出现一次的数与一个全为0的数异或，得到的数还是其本身，所以整个数组的元素全部参与异或运算，得到的数就是出现一次的数。
时间复杂度:O(n)。
空间复杂度:O(1)。

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        for(int i=1;i<nums.size();i++){
            nums[0] = nums[0] ^ nums[i];
        }

        return nums[0];

    }
};

2. 数学运算法：

解题思路:因为数组是非空整数数组，且里面的元素有一个出现一次的，其余都出现两次。假设数组中有a、b、c三个数，c只出现了一次，则2∗(a+b+c)−(a+a+b+b+c)=c即可计算出那一个出现了一次。
时间复杂度:O(n)。
空间复杂度:O(n)，不合题意。在计算(a+b+c)时需要对数组中的元素去重，不管是使用set、数组标记法或字典等方法，都得使用O(n)的辅助空间。

二、Java（异或）

class Solution {
    public int singleNumber(int[] nums) {


        for(int i = 1;i<nums.length;i++){

            nums[0] = nums[0] ^ nums[i];

        }

        return nums[0];    
    }
}

三、Python（异或）

1. 异或法：

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

2. 列表法：

解题思路:遍历数组，把数组中的元素加入到一个新的list当中，加入之前做判断，如果已经在列表当中，则移除该元素，到最后列表中只存在一个出现次数为1的数。
时间复杂度:O(n²),不合题意。遍历一遍数组时间为O(n)，但是使用not in时，python也会有一次遍历，所以为O(n²)。若使用异常来添加或删除数组元素，时间复杂度可降为O(n)。把判断改为:

for i in nums:
    try:
         tmp.remove(i)
    except:
        tmp.append(i)

空间复杂度:O(n)，不合题意。

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

3. 字典(hashtable)

解题思路:思路和列表法类似，遍历数组， 把数组元素的值作为key加入到字典当中，并且把value值设为1。加入时做判断，如果已经存在该key，则删除，最后的字典状态为：{出现次数为1的值：1}。
时间复杂度:O(n)。使用异常来添加或删除时时间复杂度为O(n)，如果使用判断的形式，时间复杂度为O(n²)。
空间复杂度:O(n)，不合题意。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hash_table = {}
        for i in nums:
            try:
                hash_table.pop(i)
            except:
                hash_table[i] = 1
        return hash_table.popitem()[0]

四、各语言及算法时间复杂度

各语言及算法时间复杂度