题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
规则示例
规则:
你的算法最好是O(n)时间复杂度,不使用额外空间来实现
示例1:
输入: [2,2,1]
输出: 1
示例2:
输入: [4,1,2,1,2]
输出: 4
粗暴解题分析:
这道题如果不考虑时间和空间复杂度有非常多种解决方案
1.两次循环暴力排查
直接两个循环嵌套判断重复与否,如果内部循环遍历完没有发现重复,则认为找到目标值
2.List容器存储
遍历数组,如果List容器中存在当前值则移除,如果不存储在则存储,最后只会留下一个不重复的数
3.Dictionary容器存储
字典中键存储数组中数值,值存储出现次数。最后得到出现次数为1的则为结果
粗暴解题:
1.两次循环暴力排查
2.List容器存储
3.Dictionary容器存储
优雅解题分析:异或位运算
以上的3种暴力解题方法都不能满足题目中的规则:
算法最好是O(n)时间复杂度,不使用额外空间来实现
做这道题的关键是抓住题中的两次这个关键词
重复的数字始终会出现两次,不会多也不会少
那么我们完全可以利用位运算中的异或运算来解决该问题
假设有一个整数:a
异或符号为:^
该题中可以利用的异或运算特点:
相同为0,不同为1
一个数异或0等于自己 ===> a ^ 0 = a
一个数异或自己等于0 ===> a ^ a = 0
异或运算满足交换律和结合律
a ^ b ^ a = a ^ a ^ b = b ^ (a ^ a) = b ^ 0 = b
知道了异或的这些特点,那么这道题变得极其简单
只需要遍历数组让其不停异或便能得到最终结果
优雅解题:异或位运算
总结
如果在笔试中遇到该题,使用异或位运算解题省时又省力!
END