题解 | #数组中只出现一次的数（其它数出现k次）#

题意整理

• 给定一个数组。
• 求数组中只出现一次的数。

方法一（哈希表）

1.解题思路

记录数组中每一个数出现的次数，并将数组中的数作为键，出现次数作为值添加到哈希表中，然后遍历哈希表，当某个键对应的值为1时，直接返回对应的键，即找到了只出现一次的数。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int一维数组 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        //新建map，用于计数
        Map<Integer,Integer> map=new HashMap<>();
        //将数组中所有元素出现次数添加到map
        for(int a:arr){
            map.put(a,map.getOrDefault(a,0)+1);
        }
        //如果键为1，说明只出现了一次，直接返回
        for(Integer key:map.keySet()){
            if(map.get(key)==1){
                return key;
            }
        }
        return -1;
    }
}

3.复杂度分析

• 时间复杂度：两次循环都是线性遍历，执行次数不超过n，所以时间复杂度是 。
• 空间复杂度：需要额外大小为n的哈希表，所以空间复杂度为 。

方法二（位运算）

1.解题思路

• 首先创建一个bit数组，用于记录二进制位的变化。
• 然后遍历bit数组，将原数组中元素对应bit位的1添加到bit数组，如果某个数出现k次，那么对k取余之后，对应bit位就会变成0，所以剩下的bit位一定是只出现一次的那个数的。
• 最后从高位往低位依次还原只出现1次的那个数。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int一维数组 
     * @param k int 
     * @return int
     */
    public int foundOnceNumber (int[] arr, int k) {
        //计算每一个数的bit位
        int[] bit=new int[32];

        //遍历每一个bit位
        for(int i=0;i<32;i++){
            //如果某个数出现k次，bit位累加之后就会变为k
            for(int a:arr){
                bit[i]+=((a>>i)&1);
            }
            //取余后只剩下出现一次那个数的bit位
            bit[i]%=k;
        }

        int res=0;
        //从高位往低位依次还原只出现1次的那个数
        for(int i=31;i>=0;i--){
            res=(res<<1)|bit[i];
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：第一层循环固定32次，第二层n次，总共需要循环 次，所以时间复杂度是 。
• 空间复杂度：需要额外常数级别(大小为32)的bit数组，所以空间复杂度为 。