给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只 出现了一次的元素。说明:算法应该具有线性时间复杂度。可以不使用额外空间来实现吗?
时间: 2023-12-05 21:25:35 浏览: 165
可以使用异或操作来解决这个问题。因为任何数异或自己都等于0,任何数异或0都等于它本身,因此,我们可以对数组中所有元素进行异或操作,最终得到的结果就是那个只出现一次的元素。
这个算法的时间复杂度是O(n),空间复杂度是O(1)。具体实现可以参考下面的代码:
```
int singleNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); i++) {
res ^= nums[i];
}
return res;
}
```
其中,^是异或操作符。
阅读全文
相关推荐


