每日刷题（一）——只出现一次的数字

前言

今天遇到一个位运算的题目，感觉很有意思，记录一下。

Question1

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

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

Solution

拿到题目，可以首先可以想到最暴力的解法，首先遍历整个数组，将每个元素的数量都存在map中，随后遍历map即可得出答案。时间复杂度O（N）、空间复杂度O（N）。显然不满足常量额外空间的要求。

更优一点的方法是使用异或操作，因为对同一个数的两次异或会返回原值（异或还经常用于加密领域，有一类密码叫做异或密码）。声明一个变量，随后遍历整个数组，对每个数都与此变量进行一次异或操作，最后这个值就是答案。

Code

func singleNumber(nums []int) int {var temp intfor _ , v := range nums{temp ^= v}return temp}

Question2

137. 只出现一次的数字 II

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

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

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

Solution

同样的，这题的暴力解法也可以使用map，但是会有额外的O（N）空间复杂度。

这题异或好像使用不了，因为都是奇数，查看题解后发现，居然可以统计每一个比特位1的个数，将其做余3的操作后，就可以得到答案中此比特位的位。所以遍历31次，得到每一个比特位的值，再拼接成最后的答案即可。时间复杂度为O（32N）= O（N），空间复杂度为O（1），代码如下：

Code

func singleNumber(nums []int) int {result := int32(0)for i := 0; i < 32; i++ {num:=int32(0)for _,v := range nums {num	+=  (int32(v) >> i) & 1}if num % 3 > 0{result |= (1<<i)}}return int(result)}

Question3

137. 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

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

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

Solution

同样的，这题的暴力解法也可以使用map，但是会有额外的O（N）空间复杂度。

这题可以使用异或来做，首先定义一个变量，将所有的数都与此变量进行异或，最后得到的结果就是两个只出现一次的异或的值。

通过这个值将nums里面的元素分为两组（两组中分别包含一个答案），对两组分别 使用异或，最后得到结果。

如何进行分组呢，我们的目的是两组汇总分别包含一个答案，所以可以根据两者的异或值，来找到某一个不一样的比特位，通过此比特位进行分组即可，代码如下：

Code

func singleNumber(nums []int) []int {
// 获得两个答案的异或值temp := 0for i := 0; i < len(nums); i++ {temp ^= nums[i]}//找到temp中第一个为1的比特位，根据异或的原理，说明在这个比特位上，两个答案一个为1，一个为0，以此比特位作为分组的依据index := 0for i := 0; i < 32; i++ {if (temp << i) & 1 == 1{index = ibreak}}var ans1 intvar ans2 intfor i := 0; i < len(nums); i++ {if (nums[i]<<i) & 1 == 0{ans1 ^= nums[i]}else{ans2 ^= nums[i]}}return []int{ans2,ans1}
}

总结

对于位运算的题目，要思考与、或、非、异或等操作，来合理完成题目的要求。