📃 题目描述

题目链接：

• 136. 只出现一次的数字 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

说明：

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

示例 1:

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

示例 2:

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

🔔 解题思路

算是面试高频题了

主要利用二进制中异或的特征

0 ^ 1 = 1

0 ^ 0 = 0

也就是，二进制中，0 和任意数的异或结果都是任意数本身

所以，两个相同的二进制数进行异或，就是 0

已知数组中除了某个元素只出现一次以外，其余每个元素均出现两次

依次执行异或操作，最终的出来的结果就是那个只出现一次的元素

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

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(N)