LeetCode每日一题: 136. 只出现一次的数字

墨蓝 2022-11-10 14:22 138阅读 0赞

> 微信公众号：**Java随笔录**  
> 关注可了解更多Java相关的技术分享。问题或建议，欢迎公众号留言！

### 文章目录 ###

*   *   *  题目
         *  题目大意
         *  解题思路
         *  代码
         *  执行结果
         *  公众号

### 题目 ###

*  [https://leetcode-cn.com/problems/single-number/][https_leetcode-cn.com_problems_single-number]

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

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

**示例**：

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

### 题目大意 ###

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了 一次的元素。要求算法时间复杂度是线性的，并且不使用额外的辅助空间。

### 解题思路 ###

题目要求不能使用辅助空间，并且时间复杂度只能是线性的。

题目为什么要强调有一个数字出现一次，其他的出现两次？这让我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现依次的数字，因为那些出现两次的数字全部在异或中抵消掉了。于是最终做法是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的 异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。利用的性质是**x^x = 0**。

### 代码 ###

public int singleNumber(int[] nums) { 
        int ans = 0;
        for (int num : nums) { 
            ans ^= num;
        }
        return ans;
    }

### 执行结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]

### 公众号 ###

*  关注公众号，即时接收关于Java的技术分享！

![20210207183855124.JPG][]

[https_leetcode-cn.com_problems_single-number]: https://leetcode-cn.com/problems/single-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/0de1244fcc0340afb800acdaa489e9e0.png
[20210207183855124.JPG]: https://img-blog.csdnimg.cn/20210207183855124.JPG