LeetCode题解：只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次外，其余每个元素均出现两次。找出那个只出现一次的元素。
前提：你的算法应该具有线性的时间复杂度。你可以不使用额外空间来实现吗？

示例

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

方法思路

如果这个题没有前提条件，那么解法就很多。

哈希法

首先，是最容易想到的，利用哈希表来实现。
哈希表的Key和Value分别存储数出现的次数和数的值。
虽然这种方法是最易理解的，但是其时间开销非常高。

class Solution {
    public int singleNumber(int[] nums) {
        int length = nums.length;
        int i = 0;
       Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
       while(i<length){
           int j=0;
           for(int n=0;n<length;n++){
               if(nums[i]==nums[n]){
                   j++;
               }
           }
           hash.put(j,nums[i]);
           i++;
       }
       return hash.get(1);
    }
} 

复杂度分析

• 时间复杂度：O(n^2)。
• 空间复杂度：O(n)，主要为哈希表的开销。

位运算

1、任何数和0做异或运算，结果仍然是原来的数，即a⊕0=a。
2、任何数和其自身做异或运算，即a⊕a=0。
3、异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

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

复杂度分析

• 时间复杂度：O(n)，其中n是数组长度。只需要对数组遍历一次。
• 空间复杂度：O(1)。