老卫带你学---leetcode刷题(137. 只出现一次的数字 II)

137. 只出现一次的数字 II

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3
1
2
3
4

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99
1
2
3
4

提示：

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

解决：

因为其他每个元素出现三次，那么理论上各个数字最终二进制的数字，模3就是只出现1次的数字

比如 3335
那么二进制就是 0011 0011 0011 0101，最终的二进制就是 0134，然后模3，就得到0101，就是5。这个很好理解，多想下就行

那因为0134并不是标准的二进制，二进制只有01，那么就需要利用位运算来进行状态转化

因为有3，所以最少需要两位，那两位的二进制有00，01，10，然后只有n=1的时候才会发生状态变化。

那么就是

if j==0:
	if n==0:
		i = i
	if n==1:
	    i = ~i
if j == 1:
	i = 0
1
2
3
4
5
6
7

对应的位运算就是

i=(i^n) &^ j 
1

func singleNumber(nums []int) int {
	i, j := 0,0
	for _,n := range nums{
		j = (j^n) &^ i
		i = (i^n) &^ j
	}
	return j
}
1
2
3
4
5
6
7
8