当前位置 博文首页 > 数据结构和算法：剑指 Offer 56 - II. 只出现一次的数字 II
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
//先把数字存储到map中，其中key存储的是当前数字，value是
//数字的出现的次数
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//最后在遍历map中的所有元素，返回value值等于1的
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1)
return entry.getKey();
}
return -1;
}
视频链接
再来看下代码
public int singleNumber(int[] nums) {
//最终的结果值
int res = 0;
//int类型有32位，统计每一位1的个数
for (int i = 0; i < 32; i++) {
//统计第i位中1的个数
int oneCount = 0;
for (int j = 0; j < nums.length; j++) {
oneCount += (nums[j] >>> i) & 1;
}
//如果1的个数不是3的倍数，说明那个只出现一次的数字
//的二进制位中在这一位是1
if (oneCount % 3 == 1)
res |= 1 << i;
}
return res;
}
// n是出现的次数
public int findOnce(int[] nums, int n) {
int bitLength = 32;
int res = 0;
for (int i = 0; i < bitLength; i++) {
int oneCount = 0;
for (int j = 0; j < nums.length; j++) {
oneCount += (nums[j] >>> i) & 1;
}
if (oneCount % n != 0)
res |= (1 << i);
}
return res;
}
来看下代码
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int c : nums) {
//防止a的值被修改，在计算b的时候有影响，
//这里在b计算完之后再对a赋值
int tempa = ~a & b & c | a & ~b & ~c;
b = ~a & ~b & c | ~a & b & ~c;
a = tempa;
}
return b;
}
来看下代码
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int c : nums) {
//防止a的值被修改，在计算b的时候有影响，
//这里在b计算完之后再对a赋值
int tempa = ~a & b & c | a & b & ~c;
b = ~a & ~b & c | ~a & b & c | ~a & b & ~c | a & b & ~c;
a = tempa;
}
return b;
}
来看下代码
public int singleNumber(int[] nums) {
//因为默认是001，所以c的位置我们让他全部变为1
int a = 0, b = 0, c = - 1;
for (int d : nums) {
int tempa = ~a & b & ~c & d | a & ~b & ~c & ~d;
int tempb = ~a & ~b & c & d | ~a & b & ~c & ~d;
c = a & ~b & ~c & d | ~a & ~b & c & ~d;
a = tempa;
b = tempb;
}
return b;
}
看到这里大家是不是有想法了，上面选择两位，三位都可以计算，那么四位能不能计算呢，其实也是可以的。在java中int是32位，只要不是选择1位，无论你选择2位还是28位还是32位其实都是可以的，只要满足让他出现3次的时候回到初始状态即可。那这样写下去答案就比较多了，这里就不在一直往下写了,如果感兴趣的大家可以试着写下。
