137. 只出现一次的数字 II - 力扣（LeetCode） (leetcode-cn.com)
难度：中等
题目描述：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
分析：
分析：
1- 这类题可以简单的使用HashMap进行存储，key值为数组元素，value值为元素出现的次数，最后遍历一遍，输出value为1的key即可。
2- 进阶方法可以使用位数统计的方法进行解题。
首先数组中的数都是int类型的数，转换成二进制为32位，
每个相同的元素具有相同的二进制，这是不可否认的，
我们只需要统计二进制每一位置上出现的次数，将其存放在数组count中，
再将每一位数进行mod3操作，最后数组中剩余的就是只出现一次的数的二进制形式
例如：nums = [1,1,1,3] ---> [0001,0001,0001,0011] (由于数值较小，使用4位来表示，实际存储为32位数据)
count = [0,0,0,0] ---> [0,0,1,4]
count mod 3 = [0,0,1,1] 即3的二进制表达形式。
方法二的优化：
方法二中对于一个数取各个位上的数据时,需要循环32次，当数据值小的时候这是非常不合理的
因为高位都是0，所以优化一下，让其高位都是0的情况下跳出循环。
解题
方法一：哈希表法
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> maps = new HashMap<>();
for (int num :
nums) {
if (maps.containsKey(num)) {
maps.put(num, maps.get(num)+1);
} else {
maps.put(num, 1);
}
}
for (int num :
maps.keySet()) {
if (maps.get(num) == 1) return num;
}
return -1;
}
}
方法二：位计数法
class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
for (int num :
nums) {
for (int i = 0; i < 32; i++) {
if (((num >> i) & 1) == 1) {
count[i]++;
}
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
if ((count[i] % 3) != 0) {
result += (1<<i);
}
}
return result;
}
}
方法二优化
class Solution {
public int singleNumber(int[] nums) {
int[] count = new int[32];
for (int num :
nums) {
for (int i = 0; i < 32; i++) {
if ((num >> i) == 0) {
break;
}
if (((num >> i) & 1) == 1) {
count[i]++;
}
}
}
int result = 0;
for (int i = 0; i < 32; i++) {
if ((count[i] % 3) != 0) {
result += (1<<i);
}
}
return result;
}
}
