【C++刷题】力扣-#136-只出现一次的数字
题目描述
给定一个整数数组 nums，其中除了一个数之外，其它所有数字都出现了两次。找出这个只出现一次的数字。
示例
示例 1:
输入: nums = [2,2,3,2]
输出: 3
示例 2:
输入: nums = [0,1,0,1,0,1,99]
输出: 99
题解
这个问题可以通过使用位运算来解决。由于数组中除了一个数之外其它所有数字都出现了两次，我们可以利用异或运算（XOR）的性质，即相同数字异或的结果为0，来找出这个只出现一次的数字。
- 初始化：设置变量 result 为0。
- 遍历数组：对数组中的每个数字执行异或操作。
○ 对于每个数字 num，更新 result 为 result ^ num。 - 返回结果：遍历结束后，result 就是只出现一次的数字。
代码实现
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
复杂度分析
● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可找到只出现一次的数字，且不需要额外的存储空间。