Golang面试考题记录 ━━ 只出现一次的数字，学习异或^=处理

77 阅读 0 评论 51 点赞

我是靠谱客的博主大气板栗，最近开发中收集的这篇文章主要介绍Golang面试考题记录 ━━ 只出现一次的数字，学习异或^=处理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

===问：

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

说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

===答：

方法一：执行82.17%，内存0%完败
用了两次循环，且用了map

func singleNumber1(nums []int) int {
temp := make(map[int]int, len(nums))
for _, v := range nums {
temp[v]++
}
for i, v := range temp {
if v == 1 {
return i
}
}
return 0
}

方法二：执行0.00%完败，内存100%
嵌套循环，执行速度最慢

func singleNumber2(nums []int) int {
for i, v := range nums {
r := 0
for j, y := range nums {
if i != j && v == y {
r++
}
}
if r == 0 {
return v
}
}
return nums[len(nums)-1]
}

方法三：执行82.27%完败，内存64.85%||100.00%
使用了异或的方法，性价比最高，但是，但是，但是，仅仅适用于本题，后面详解。

func singleNumber3(nums []int) int {
c := 0
for _, v := range nums {
c ^= v //c = c ^ v
}
return c
}

===解：

参考：leetcode go语言刷题只出现一次的数字

只有一个出现一次，其他元素均出现两次，那么数组长度肯定是奇数，只要先排序在两两比较就可以找到出现一次的数字了。
但是题目提出了要求：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
这个要求就增加了难度，似乎进入了死胡同。这时候就要想到一些黑魔法，例如异或。
异或（^）【同0异1】
运算规则：0^0=0；01=1；1^0=1；11=0；
用途：
（1）使特定位翻转，异或上一个要翻转位数为1，其余位为0的数值即可。
例：设x=11101100，将x的低四位翻转。令x^00001111=11100011
（2）与0异或，保留原值。
（3）基于异或运算，不引用新变量，交换两个变量的值
可以发现相同的数字进行异或那么得到的值为0，任何数字同0异或得到的都是其本身。
所以这道题用异或就可以了。

举个具体的例子

v := 0
//1、 0的二进制：0
v ^= 32 //2、32的二进制：0100000，异或后得值：0100000（32）
v ^= 64 //3、64的二进制：1000000，异或后得值：1100000（96）
v ^= 5
//4、 5的二进制：0000101，异或后得值：1100101（101）
v ^= 15 //5、15的二进制：0001111，异或后得值：1101010（106）
v ^= 64 //6、64的二进制：1000000，异或后得值：0101010（42）
v ^= 32 //7、32的二进制：0100000，异或后得值：0001010（10）
v ^= 15 //8、15的二进制：0001111，异或后得值：0000101（5）
// 此处已经得到正确结果5
v ^= 15 //9、15的二进制：0001111，异或后得值：0001010（10）