题目一(数组中只出现一次的两个数字)描述：
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例：

输入：[1,4,1,6]
返回值：[4,6]
说明：返回的结果中较小的数排在前面  

方法一：哈希表
已经总结过所有与元素次数相关的问题都可以用哈希表解决。

import java.util.*;
public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            int count = map.getOrDefault(array[i], 0);
            map.put(array[i], count + 1);
        }
        for (Integer i : map.keySet()) {
            if (map.get(i) == 1) {
                result[index] = i;
                index++;
            }
        }
        if (arr[0] > arr[1]) {
            swap(arr); // 将较小的数放在前面
        }
        return result;
    }
    private void swap(int[] arr) {
        int temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;
    }
}

时间复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( n ) O(n) O(n)。
方法二：位运算
假设数组中两个数字(a, b)只出现一次，其余数字都出现两次，说明a和b必然不相等，它们的二进制也就不相同，则a和b异或的结果不等于0。先将数组中的所有整数进行异或，结果为result，由于其它元素都出现两次，异或满足交换律，所以最终的结果就等于a和b异或的结果，即result = a ^ b，且result不等于0。result二进制从低位到高位，在第一个为1的位置，a和b二进制在此位置不相等(设a在此位置为0，b在此位置为1，这样异或的结果在此位置才为1)。找到result二进制从低位到高位第一个为1的位置，result = result & (-result)，此时假设result结果为0000 1000，说明a的二进制在第3位是0，b的二进制在第3位是1，据此将原数组中的元素划分为两组。一组：元素第3位是0，则该元素 i & result 结果为0，arr[0] ^= i，a被分到该组，arr[0]异或的最终结果就是a；另一组：元素的第3位是1，则该元素 i & result 结果不为0，arr[1] ^= i，b被分到该组，arr[1]异或的最终结果就是b。返回arr之前，先判断arr[0]和arr[1]的大小，如果arr[0] > arr[1]，则交换arr[0]和arr[1]，使得较小的数在前面。

import java.util.*;
public class Solution {
    public int[] FindNumsAppearOnce (int[] array) {
        int[] arr = new int[2];
        int result = 0;
        for (int i: array) {
            result ^= i;
        }
        result = result & (-result); // 从低位到高位开始，第一个二进制位是1的位置
        for (int i: array) {
            if ((i & result) == 0) {
                arr[0] ^= i;
            } else {
                arr[1] ^= i;
            }
        }
        if (arr[0] > arr[1]) {
            swap(arr);
        }
        return arr;
    }
    private void swap(int[] arr) {
        int temp = arr[0];
        arr[0] = arr[1];
        arr[1] = temp;
    }
}

时间复杂度：遍历数组每一个元素，进行异或， O ( n ) O(n) O(n)；空间复杂度： O ( 1 ) O(1) O(1)。

题目二(数组中只出现一次的唯一数字)描述 ：
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例：

示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1

方法一：哈希表
采用哈希表的方法非常简单，不再叙述过程。

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num: nums) {
            int count = map.getOrDefault(num, 0);
            map.put(num, count + 1);
        } 
        
        for(Integer num: map.keySet()) {
            if(map.get(num) == 1) {
                return num;
            }
        }
        return -1;
    }
}

时间复杂度： O ( n ) O(n) O(n)，空间复杂度： O ( n ) O(n) O(n)。
方法二：位运算
由于其余重复的数字出现三次，如果使用异或位运算，结果还是这个重复的数字，所以本题无法使用异或位运算。对于重复的数字，将其二进制中对应的位置求和，则二进制每个位置的总和能被3整除。如果再加上这个只出现一次的整数，二进制中对应的每一位能被3整除，则说明这个只出现一次的数的二进制对应位置为0；如果加上这个只出现一次的整数，二进制中对应的每一位不能被3整除，则说明这个只出现一次的数的二进制对应位置为1。所以总的思路是先求数组中所有整数的二进制对应位的总和，再通过二进制形式求得这个只出现一次的整数。

class Solution {
    public int singleNumber(int[] nums) {
        int[] bitSum = new int[32];
        for (int i = 0; i < nums.length; i++) {
            int flag = 1;
            for (int j = 31; j >= 0; j--) {
                if ((nums[i] & flag) != 0) {
                    bitSum[j] += 1;
                }
                flag = flag << 1;
            }
        }
        // 所有整数的每位二进制求和结束
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = result << 1;
            result += bitSum[i] % 3;
        }
        return result;
    }
}

时间复杂度：虽然有双层for循环，但是内层for循环的时间复杂度为 O ( 1 ) O(1) O(1)，所以总的时间复杂度为 O ( n ) O(n) O(n)；算法中需要开辟32个元素空间，仍然是常量阶，所以空间复杂度为 O ( 1 ) O(1) O(1)。

---

结束语：如果本篇博客对您有帮助，请点赞、收藏或关注，您的鼓励是博主进步的动力，感谢支持，共同进步。