【异或的巧妙使用】求只出现一次的数字

80 阅读 0 评论 53 点赞

我是靠谱客的博主灵巧帽子，最近开发中收集的这篇文章主要介绍【异或的巧妙使用】求只出现一次的数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

此题目来源于LeetCode，感兴趣的同学可以去官网练习。

题目描述：

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

说明：

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

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

解答：

int singleNumber(int* nums, int numsSize){
    return numsSize==1?nums[0]:(singleNumber(nums+1,numsSize-1)^nums[0]);
}

由于此题目比较特殊，有且仅有一个不为两次出现的元素，所以这里使用了异或的原理：相同的数据异或之后为0，如:

a^b^b = a^0 = a

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。