一、题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:算法应该具有线性时间复杂度。 并且不能使用额外空间来实现。

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

我的实现:借鉴217题方法二的实现算法。先将数组排序,再进行下一步讨论。
代码如下:

int cmpfuc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

int singleNumber(int* nums, int numsSize)
{
    if(numsSize == 1)   // 特殊情况判断,只有一个元素时直接返回
        return nums[0];
    
    qsort(nums, numsSize, sizeof(int), cmpfuc);     // 先对数组排序

    int res = 0;
    for (int i = 0; i <= numsSize - 1; i += 2)
    {
        if(i == numsSize - 1 || nums[i] != nums[i + 1])
        {
            res = nums[i];
            break;
        }
    }
    return res;
}

二、解决方案

方案一:列表操作

算法

  1. 遍历 nums 中的每一个元素
  2. 如果某个 nums 中的数字是新出现的,则将它添加到列表中
  3. 如果某个数字已经在列表中,删除它

方案二:哈希表

算法
我们用哈希表避免每次查找元素是否存在需要的 O(n)O(n) 时间。

  1. 遍历 nums 中的每一个元素
  2. 查找 hash_table 中是否有当前元素的键
  3. 如果没有,将当前元素作为键插入 hash_table
  4. 最后,*hash_table *中仅有一个元素,用 popitem 获得它

注:上述方案一、二适合python语言实现,读者可以自行动手实现。


方案三:数学

根据题目意思,可以发现有如下数学关系式:

2(a+b+c)(a+a+b+b+c)=c2 * (a + b + c) - (a + a + b + b + c) = c

C代码如下:

int cmpfuc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

void arrElementDelete(int* nums, int length, int k)
{
    // delete the element, which's position is k
    for (int i = k; i < length - 1; i++)
    {
        nums[i] = nums[i + 1];
    }
}

void removeDumplicates(int* nums, int length, int* cnt)
{
    // sort the array
    qsort(nums, length, sizeof(int), cmpfuc);

    // delete the same elements
    for (int i = 0; i < length - 1; i++)
    {
        if (nums[i] == nums[i + 1])
        {
            arrElementDelete(nums, length, i);
            length -= 1;
            *cnt += 1;
        }           
    }
}

int arrSum(int* nums, int length)
{
    int sum = 0;
    for (int i = 0; i < length; i++)
    {
        sum += nums[i];
    }
    return sum;
}

int singleNumber(int* nums, int numsSize) 
{
    int sum1 = arrSum(nums, numsSize);

    int num = 0;
    int* deleteNums = &num;
    removeDumplicates(nums, numsSize, deleteNums);
    int length = numsSize - *deleteNums;
    int sum2 = arrSum(nums, length);

    int res = 2 * sum2 - sum1;
    return res;
}

方案四:位操作

相关概念

  • 如果我们对 0 和二进制位做 XOR 运算,得到的仍然是这个二进制位
    a \oplus 0 = a
  • 如果我们对相同的二进制位做 XOR 运算,返回的结果是 0
    a \oplus a = 0
  • XOR 满足交换律和结合律
    a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b
    所以我们只需要将所有的数进行 XOR 操作,得到那个唯一的数字。

代码如下:

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

复杂度分析:

  • 时间复杂度: O(n)O(n) 。我们只需要将 {nums} 中的元素遍历一遍,所以时间复杂度就是 {nums} 中的元素个数。
  • 空间复杂度:O(1)O(1)