剑指offer 56-2仅仅一个数x出现一次，其余出现三次，找x

101 阅读 0 评论 67 点赞

我是靠谱客的博主单纯水杯，这篇文章主要介绍剑指offer 56-2仅仅一个数x出现一次，其余出现三次，找x，现在分享给大家，希望可以做个参考。

题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

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

##题目分析：
可以用两种方法。

位运算
求和法。这种要注意求完和有可能会很大，超过int范围，所以要将和的变量定义为long，最后再强制转为int。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//方法一：位运算
class Solution {
public int singleNumber(int[] nums) {
//方法一：利用位运算
//将每个元素的二进制按位分别进行相加，得到的每一位的1的个数之后2中情况：3的倍数或者3的倍数+1，那么这个+1就是目标值带来的
int res = 0;
for(int i = 0; i < 32; i++){
int cnt = 0;
for(int j = 0; j < nums.length; j++){
if((nums[j] >> i & 1) == 1){//右移nums[j]的二进制，与1，即可该位是否等于1，右移就是把右边的一位挤掉，所以每次可以将当前位变为最右边的，从而与1相与。
cnt++;
}
}
if(cnt % 3 != 0){//该位与目标值有关
res = res | 1 << i;
}
}
return res;
}
}
//求和方法
class Solution {
public int singleNumber(int[] nums) {
//用求和的方法，需要哈希表的辅助
//先求所有数的和
//易错点：有个样例求完和值会很大，会超出int范围，所以定义为long
long addAllNum = 0;
long addHashSet = 0;
HashSet<Integer> set = new HashSet<>();
for(int num : nums){
addAllNum += num;
if(!set.contains(num)){
set.add(num);
addHashSet += num;
}
}
//addHashSet * 3 - addAllNum = 2*目标值
int res = (int)((addHashSet * 3 - addAllNum) / 2);
return res;
}
}