LEETCODE 136. Single Number 解题思路分析

题目大意：

只出现一次的数字

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

说明：

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

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=136

解题思路分析：

本题实际上是异或运算的经典应用场景。在二进制运算中，两个不同的数字异或结果为1，相同数字的异或结果为0。如果在十进制数中，两个相同数字的异或依旧是0，而0和任意一个数的异或结果是那个任意的数字。

回到本题，因为题目中除了那个单独的数字之外都是两两相同的数字，因此除了单独数字之外的所有数字异或后的结果应该是0，而0和那个单独数字的异或结果就是那个单独的数字，也就是本题的返回结果。

所以本题的解法很简单，返回所有数字的异或结果即可。

实现代码：

public int singleNumber(int[] nums) {
    int res=nums[0];
    for(int i=1;i<nums.length;i++){
        res^=nums[i];
    }
    return  res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Single Number.

Memory Usage: 40.2 MB, less than 94.07% of Java online submissions for Single Number.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-136-single-number-解题思路分析/