题目描述

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

说明：

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

示例 1:
输入: [2,2,1]输出: 1
示例 2:
输入: [4,1,2,1,2]输出: 4
链接：https://leetcode.cn/problems/single-number/description/

思路分析

• 今天的算法题目是数组类型题目。题目要求找出只出现一次的元素。求数组元素出现的次数，首先想到的是使用 hashMap 记录每一个元素出现的次数，然后在找到出现一次的元素，hashMap 算法的时间复杂度是 O(n), 空间复杂度是 O(n)。

• hashMap 的解法可以通过测试用例。但是，题目还有额外的要求，“你可以不使用额外的空间吗？”这就有了一定的难度，百思不得其解。于是，我查看题解，题解中指出了位运算这种解法，具体来说就是使用异或运算。异或运算满足交换律，a^b^a=a^a^b=b,因此 ans 相当于 nums[0]^nums[1]^nums[2]^nums[3]^nums[4]..... 然后再根据交换律把相等的合并到一块儿进行异或（结果为 0），然后再与只出现过一次的元素进行异或，这样最后的结果就是，只出现过一次的元素。具体实现代码如下，供参考。

通过代码

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

总结

• 上述算法的时间复杂度是 O(n),空间复杂度是 O(1)

• 今天的算法题目是位运算应用题目，想要掌握好位运算，需要熟记计算规律和法则，熟记之后才能熟练应用，提升解题效率。

• 坚持算法每日一题，加油！我会继续更新，也欢迎算法爱好者一起交流学习。