剑指offer004(Java)-只出现一次的数字（中等）

题目：

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例1：

输入：nums = [2,2,3,2]

输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,100]

输出：100

提示：

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

注意：本题与 力扣 137 题相同：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/WGki4K
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

方法一：位运算

利用int类型固定为32位，利用这32位来统计每一个数值的每一位出现1的次数，然后再对每一位统计出的次数与3进行模运算（如果出现3次，那模运算一定为0），模运算不为0时，就让1向右移动，再与结果进行或运算。

举个例子：[1,1,1,3],1的二进制为 :0001， 3的二进制为：0011

1： 0 0 0 1
1： 0 0 0 1
1： 0 0 0 1
1： 0 0 1 1
c： 0 0 1 4 

当count =4时，count % 3 != 0，res |= (1 << 0) = 0000 | 0001 = 0001

当count = 1时， count % 3 != 0，res |= (1 << 1) = 0001 | 0010 = 0011

当count = 0时， count % 3 = 0，不更新res

...（后面的位都不更新res）

结束时res = 0011 = 3

图片来源：K神老师

代码：

 1 class Solution {
 2     public int singleNumber(int[] nums) {
 3         int res = 0;
 4         //数组中的元素都在int（即 32 位整数）范围
 5         //第一个循环 i从 0~31 ，代表每一位2进制数
 6         for (int i = 0; i < 32; i++){
 7             int count = 0;
 8             for(int num : nums){
 9             // num >> i表示num右移i位置，即把二进制第i位右移到最右边
10             // & 1右移之后与1进行&运算，即得到最右边的数
11             //(num >> i) & 1 举例：num为5,i为2，num二进制为 0101，num>>2&1 = 0001 & 1 = 0001 = 1
12                 count += ((num >> i) & 1);
13             }
14             //count为nums数字中所有数的二进制第i位的和
15             //count%3！=0：目标答案 二进制的第i位为1
16             if (count % 3 != 0){
17                 // 1 << i，将1左移i位，例如i为2，1 << i得到二进制数：100
18                 // 将1左移i位之后，与ans即目标答案进行 | 运算（或运算）
19                // 或 运算的目的就是把 第i位的这个1加到ans里
20                //例如：res = 0 |= 0010 = 0010
21                //继续：res = 0010 |= 0001 = 0011 = 3 
22                 res |= (1 << i);
23             }
24         }
25         return res;
26     }
27 }

方法二：哈希表但空间复杂度和时间复杂度均为O(n)

 1 class Solution {
 2    public int singleNumber(int[] nums) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for(int num : nums){
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7         for (int num : map.keySet()){
 8             if (map.get(num) == 1) return num; 
 9         }
10         return -1;
11    }
12 }