1 题目描述
2 题目解读
在非空整数数组nums中，有一个元素只出现了一次，其余元素均出现两次。要求找出那个只出现一次的元素。
3 解法一：位运算
位运算，是一种非常简便的方法。
3.1 解题思路
异或运算，有以下三个性质。
（1）任何数和0做异或运算，结果仍然是原来的数；
（2）任何数和其自身做异或运算，结果是0；
（3）异或运算满足交换律和结合律。
3.2 设计代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e : nums) ret ^= e;
return ret;
}
};
int main()
{
vector<int> nums{ 2,2,3,1,3 };
Solution s;
int ans = s.singleNumber(nums);
cout << ans << endl;
return 0;
}
3.3 复杂度分析
- 时间复杂度：
。for循环枚举了一遍数组元素。
- 空间复杂度：
。没有使用额外数组空间。
3.4 提交结果
4 解题心得
- 位运算，是一种非常简洁且有效的运算方法。
- 异或运算，有三条性质。
- 高效的算法，对于计算机科学来说非常重要。
