题目要求

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

（LeetCode136也就是这么个题吧，简单题，要求是最好写出线性的时间复杂度和O(1)的空间复杂度）

分析

首先很容易想的就是开一个数组计数，但算法效率肯定不好。
还可能用哈希什么的去做，线性的空间能保证吗？
……
其实这问题本质上是考察 按位异或 的位运算符的。

怎么说？
学过离散数学我们知道，异或是说，同则取0，异则取1。
按位异或就是按照二进制的表示，两个数每一位同则取0，异则取1。
异或也有交换律：a ^ b = b ^ a，所以顺序无所谓的。
既然其他数都是出现两次，那我们就可以认为遍历结束后的时候，每个两两相同的数值对异或后都是0了，剩下的是那个落单的。
怎么让结果就是落单的呢？
还得从0身上下手：
a ^ 0 = a
所以说，只要初值设成0的话，遍历一趟数组，逐一异或，最终结果就是出现一次的数。

Java编程实现

class Solution {public int singleNumber(int[] nums) {int n = 0;for (int i : nums) {n ^= i;}return n;} } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的【LeetCode】查找只出现一次的数字算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。