前言
今天接到了一个面试，面试官鑫哥声音很好听，人也很好，是我目前见到的所有面试官中最好的一位啦。
可能还是知识面比较窄，第一个问题就把我给问倒了。一是太紧张，二是本身能力可能也没那么强，所以第一题没能想出来。面试完后，心里还是坠着一个石头似得，就一个想法，把这个问题搞明白，实现了。
于是下午，着手实现了一下，在此做个笔记，希望对后来人能有所帮助。
正文
这道题的内容是这样的：
给一个数组，数组中只有一个元素出现了仅仅一次，其他元素都是出现了两次。请用空间复杂度为O(1)和时间复杂度为O(n)的算法找出这个数。
说实话，我第一反应就是：“尴尬，这下完蛋了”。肯定不是正规思路了。然后就想啊想啊，最后勇于向鑫哥承认，这道题我确实没有什么好的办法。虽然很挫败，但是最起码我很诚实嘛。
def find(array):
"""
仅适用于数据连在一起的情况，如ls = [1,1,2,2,3,3,4,4,5,5,6,6,7,8,8,9,9]
:param array:
:return:
"""
temp = array[0]
index = 1
while index<len(array)-1:
if temp == array[index]:
temp = array[index+1]
index += 2
else:
return index-1
但是这个函数不能处理乱序的数组，所以肯定是不行的啦。
思路
下午就搜索了相关的解题技巧，发现这是《剑指Offer》的一道题。看来我还是准备的不够好，因为我没看过这本书呢还。如果之前看到了这本书，估计今天也不会这么尴尬了不是。改天一定要买一本，好好琢磨琢磨。
对于这道题，思路是这样的。
比如给定一个数组[1,1,2,2,3],让每一个元素与其后面的元素进行异或运算。
最终得到的结果，刚好就是那个仅出现一次的数的值。
比如对于这个数组：
循环开始
1^1 = 0 即：十进制的0
0^(10)[2] = 10 即：十进制的2
10^(10)[2] = 0 即：十进制的0
0 ^ （11）[3] = 11 即：十进制的3
循环结束
(@ο@) 哇～，是不是感觉很神奇呢？ 反正我是这么觉得。数学真的是太奇妙了。
存在一个数字
下面我用Python实现了一下，发现代码还是很少的。
def common(array):
"""
思路： 第一个数和第二个数异或运算，得到的结果再次参与到异或运算，最终得到的结果就是数组中仅仅出现一次的那个数。
:param array:
:return:
"""
position = array[0]
for index in range(1, len(array)):
position ^= array[index]
return position
输入测试数据：
ls = [1,1,2,2,3,3,4,4,5,5,6,6,7,8,8,9,9]
position = find(ls)
print("{} 出现的下标位置为：{}".format(ls[position], position))
输出内容：
7 出现的下标位置为：12
迄今为止，代码运行的效果还算不错。
存在两个数字
数组中存在一个这样的数字的情况解决了，那么如果数组中有两个仅仅出现一次的元素呢？这个时候怎么找出来？
答案是拆分数组。
把大数组拆分成两个小数组，每个小数组中仅包含一个出现一次的元素。
那么问题的关键来了，到底该怎么分呢？以什么为依据呢？怎么求得结果呢？
其实看完原理后就觉得很简单了。有如下三个步骤：
- 计算异或的最终值
- 拆分数组
- 分别计算得出结果
关键就在于第二步了。
异或得到的值的二进制表示法中肯定有一个位置（至少有一个位置）为1。
比如对于数组： 1，1，2，2，3
得到的异或值最终为11（二进制表示法）。我们按从右至左的顺序来搜索第一个1的位置。然后对数组中的其他元素的二进制表示的这个位置进行判断。如果为1，分到第一个数组中，否则分到第二个数组。
因为相同的数字，标记位一定相同，不同的数字，标记位不同，这样就达到了我们的要求。
为了实现这个功能，我们还需要几个小函数。来方便操作，分别是：
- 求一个十进制数的二进制表示法；
def get_binary_expression(number):
binarystr = []
while number!= 0:
shang = int(number /2 )
yushu = number - shang*2
binarystr.append(str(yushu))
number = shang
binarystr.reverse()
return ''.join(binarystr)
- 求一个二进制数从右至左第一个不为0的下标。
def get_noone_position(s):
# 先反序，为了找到下标
s = [item for item in s]
s.reverse()
# print(s)
s = ''.join(s)
for index in range(len(s)):
if int(s[index])==1:
return index
else:
continue
好了万事俱备，只剩分组了。
def split(array):
postfix = common(array)
flag = get_noone_position(get_binary_expression(postfix))
print(array)
subarr1 = []
subarr2 = []
# 根据第position位置上是否为1来分割数组
for item in array:
tempflag = get_noone_position(get_binary_expression(item))
# print(get_binary_expression(item))
if tempflag == flag:
subarr1.append(item)
else:
subarr2.append(item)
print(subarr1)
print(subarr2)
num1 = common(subarr1)
num2 = common(subarr2)
return num1, num2
下面我们来测试一下。
输入数据：
array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 7, 6, 5, 4, 3, 2, 1]
num1, num2 = split(array)
print("Num1: {}, Num2: {}".format(num1, num2))
输出结果：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 7, 6, 5, 4, 3, 2, 1]
[1, 3, 5, 7, 9, 7, 5, 3, 1]
[2, 4, 6, 8, 6, 4, 2]
Num1: 9, Num2: 8
发现大数组被分成了两个子数组，而且每个子数组的的确确是只包含一个出现了一次的元素。
总结
实现了这俩功能，心里的石头终于落了地。要不然总觉得少了点什么。
最后，突然发现，数学真的是好神奇，同时我也明白了，还有好多东西需要去了解，去学习。这样在用到的时候就不会手忙脚乱， 尴尬面对了。
