题解 | #只出现一次的数字#

题目主要信息

定一个整数数组，数组中有一个数出现了一次，其他数出现了两次，请找出只出现了一次的数。

注意：数组中元素个数1<n<100000 。

方法一：使用hash存储

具体方法

遍历数组，当一个数在map中未出现时，就将该数放入map中，如果当前数在map中已经出现了，就将其移出，最后map中剩下的数，就是只出现一次的数。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<>();
      // 遍历数组
        for(int num:nums){
          // 存在就移出当前值
            if(map.get(num) != null){
                map.remove(num);
            }else{
                map.put(num,1);
            }
        }// 返回map中的值
        for(int num:map.keySet()){
            if(map.get(num) == 1){
                return num;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，遍历一遍数组
• 空间复杂度：$O(n)O(n)$，最坏的情况所有的元素存入map中

方法二：位运算

具体方法

首先了解一下异或的性质。

异或运算有以下三个性质。

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

数组中的全部元素的异或运算结果即为数组中只出现一次的数字,具体可以看下面的实例。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
        // write code here
         int result = 0;
        
        for(int num:nums){
            result ^= num;
        }
        return result;
    }
}

复杂度分析

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