每日一题——只出现一次的数字

只出现一次的数字

题目链接

思路

要求为线性时间复杂度，即时间复杂度为O(n)，那么我们就不能用简单的两层循环来解决问题

要求只能使用常量额外空间，即空间复杂度为O(1)，那么我们就不能额外开辟一个数组来记录每个元素出现的次数

这里，给大家介绍一个全新的方法：位运算——异或^

注：如果对位运算符还不太了解，建议先看看👉位运算详解

异或的特性：

异或是支持交换律的：a ^ b ^ c = b ^ a ^ c

a ^ a = 0（相同的数异或为0）

0 ^ a = a（一个数和0异或得到的还是本身）

那么我们就可以利用异或的这些特性，来解决这个问题。

题目告诉我们，数组中除某一个元素只出现一次外，其余元素都出现了两次，那么我们将数组的所有元素都异或到一起，不就可以得到只出现一次的那一个数了吗？

实现代码

int singleNumber(int* nums, int numsSize)
{
    int ret = 0;
    for(int i = 0; i < numsSize; i++)
        ret ^= nums[i];
    return ret;
}

通过这一道题，最重要的就是掌握异或的特性，这有利于后续许多问题的解决