LeetCode 136. Single Number 只出现一次的数字（Java）

题目：

Given a non-empty 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?

Example 1: Input: [2,2,1] Output: 1

Example 2: Input: [4,1,2,1,2] Output: 4

解答：

解法一：HashTable (不符合题目要求)

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

只想到了使用HashTable方法，但题目要求线性时间复杂度，而且不使用额外空间，使用哈希表不符合条件。参考他人解法学习了异或运算。

解法二：异或运算

异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”，在java里用 ^ 来表示。

异或运算法则： 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）

异或运算性质： 1.恒定律：A ^ 0 = A 2.归零率：A ^ A = 0 3.交换律：A ^ B = B ^ A 4.结合律：(A ^ B) ^ C = A ^ (B ^ C)

本题中，假设数组为 [𝑎1,𝑎1,𝑎2,𝑎2,…,𝑎𝑛,𝑎𝑛,𝑎𝑥] ，其中，𝑎𝑥 只出现一次，其余的元素都出现两次，对该数组中的所有元素进行异或运算可得： 因此，只需要遍历数组中的所有元素，依次进行异或操作就可以找出只出现一次的元素。

class Solution {
          
   
    public int singleNumber(int[] nums) {
          
   
        int result=nums[0];
        for(int i=1;i<nums.length;i++){
          
   
            result^=nums[i];
        }
        return result;
    }
}