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

题意整理

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

方法一（哈希表）

1.解题思路

新建一个哈希表，然后遍历nums数组。如果出现过num，则从map中移除，如果没出现，则放入map中。最后留在map的一定是只出现一次的数字。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
        //新建哈希表
        Map<Integer,Integer> map=new HashMap<>();
        //遍历整个nums数组
        for(int num:nums){
            //如果包含num，直接从map移除
            if(map.containsKey(num)){
                map.remove(num);
            }
            //如果不包含，将键值设为1
            else{
                map.put(num,1);
            }
        }
        
        //返回map中唯一的键
        for(Integer key:map.keySet()){
            return key;
        }
        return -1;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历整个nums数组，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：最坏情况下，nums前面的数字均不重复，直接将所有的数字加入map，所以需要额外大小为$(n+1)\mathrm{/}2(n+1)/2$的map，所以空间复杂度为$O(n)O(n)$。

方法二（异或）

1.解题思路

首先需要了解异或的两个性质：

1.任意数字与0异或，结果为0。

2.两个相同的数字异或，结果为0。

只要遍历数组中所有的数字，逐个进行异或运算，最后留下的一定是只出现一次的数字。

图解展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
        //定义结果变量
        int res=0;
        //遍历整个nums数组
        for(int num:nums){
            //进行异或运算
            res^=num;
        }
        
        return res;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历整个nums数组，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：不需要额外内存空间，所以空间复杂度为$O(1)O(1)$。