leetcode 练级 - 只出现一次的数字
题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number
解题思路
异或运算的运用,很巧妙,数组中相同的数异或后都变为0了,余下的一个数与0异或还是这个数本身
异或运算的规律如下:
交换律:a ^ b ^ c <=> a ^ c ^ b
任何数与0异或为任何数 0 ^ n => n
相同的数异或为0: n ^ n => 0
代码实现
版权声明: 本文为 InfoQ 作者【幸福三寸日光】的原创文章。
原文链接:【http://xie.infoq.cn/article/d3a0f06417d01a0177172c00a】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论