C语言如何实现missingnumber算法？

问题定义

给定一个包含 n 个不同数字的数组，这些数字的范围是从 0 到 n，这个数组中恰好缺少一个数字，我们的任务就是用 C 语言找出这个缺失的数字。

示例:

• 输入: [3, 0, 1] (n=3)

• 输出: 2

• 输入: [9, 6, 4, 2, 3, 5, 7, 0, 1] (n=9)

  
  （图片来源网络，侵删）

• 输出: 8

数学求和法 (最直观)

这是最容易想到的方法,我们可以利用等差数列求和公式来解决这个问题。

思路

1. 一个完整的、从 0 到 n 的数列，其总和是 sum_total = n * (n + 1) / 2，注意，这里的 n 是数组的长度，因为数组里有 n 个数字，而完整的数列应该是 0 到 n，共 n+1 个数。
2. 计算当前给定数组中所有数字的总和 sum_array。
3. 缺失的数字就是 sum_total 和 sum_array 的差值：missing_number = sum_total - sum_array。

C 语言代码实现

#include <stdio.h>
// 函数声明
int missingNumber_sum(int* nums, int numsSize);
int main() {
    int nums1[] = {3, 0, 1};
    int size1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("数组: [3, 0, 1]\n");
    printf("缺失的数字是: %d\n", missingNumber_sum(nums1, size1)); // 应该输出 2
    int nums2[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
    int size2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("\n数组: [9, 6, 4, 2, 3, 5, 7, 0, 1]\n");
    printf("缺失的数字是: %d\n", missingNumber_sum(nums2, size2)); // 应该输出 8
    return 0;
}
/**
 * @brief 使用数学求和法寻找缺失的数字
 * @param nums 整数数组
 * @param numsSize 数组的大小
 * @return 缺失的数字
 */
int missingNumber_sum(int* nums, int numsSize) {
    // 完整数列 0 到 n 的总和，n = numsSize
    // [3,0,1], size=3, n=3, sum_total = 3*4/2 = 6
    int sum_total = numsSize * (numsSize + 1) / 2;
    int sum_array = 0;
    // 遍历数组，计算数组内元素的和
    for (int i = 0; i < numsSize; i++) {
        sum_array += nums[i];
    }
    // 缺失的数字就是总和之差
    return sum_total - sum_array;
}

优缺点

• 优点:
  • 思路非常简单直观。
  • 时间复杂度为 O(n),只需要遍历数组一次。
  • 空间复杂度为 O(1),只使用了几个变量来存储总和。
• 缺点:
  • 整数溢出风险：n 非常大，numsSize * (numsSize + 1) 这个乘积可能会超出 int 类型的表示范围，导致计算错误，虽然这在很多面试场景中不是主要问题,但在实际生产环境中需要注意。

异或法 (更优)

异或是一种位运算，它有一个非常重要的特性,非常适合解决这个问题。

思路

异或运算有以下两个核心性质：

1. 一个数和它自身异或，结果为 0： a ^ a = 0
2. 一个数和 0 异或，结果为它本身： a ^ 0 = a
3. 异或运算满足交换律和结合律： a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

我们可以利用这些性质来消除数组中所有存在的数字,最终剩下的就是缺失的数字。

1. 初始化一个变量 missing 为 n（即数组的长度）。
2. 遍历数组 i 从 0 到 n-1：
   • 将 missing 与 i 进行异或，这相当于在序列中引入了所有应该存在的索引 0, 1, 2, ..., n-1。
   • 将 missing 与 nums[i] 进行异或,这相当于从序列中移除了所有实际存在的数字。
3. 循环结束后，missing 中剩下的就是那个“只出现一次”的数字,也就是缺失的数字。

举个例子，nums = [3, 0, 1]，n = 3：

• missing = 3 (初始值)
• i = 0:
  • missing = 3 ^ 0 ^ nums[0] -> missing = 3 ^ 0 ^ 3 -> missing = (3 ^ 3) ^ 0 -> missing = 0 ^ 0 -> missing = 0
• i = 1:
  • missing = 0 ^ 1 ^ nums[1] -> missing = 0 ^ 1 ^ 0 -> missing = (0 ^ 0) ^ 1 -> missing = 0 ^ 1 -> missing = 1
• i = 2:
  • missing = 1 ^ 2 ^ nums[2] -> missing = 1 ^ 2 ^ 1 -> missing = (1 ^ 1) ^ 2 -> missing = 0 ^ 2 -> missing = 2
• 循环结束，返回 missing，结果为 2。

C 语言代码实现

#include <stdio.h>
// 函数声明
int missingNumber_xor(int* nums, int numsSize);
int main() {
    int nums1[] = {3, 0, 1};
    int size1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("数组: [3, 0, 1]\n");
    printf("缺失的数字是: %d\n", missingNumber_xor(nums1, size1)); // 应该输出 2
    int nums2[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
    int size2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("\n数组: [9, 6, 4, 2, 3, 5, 7, 0, 1]\n");
    printf("缺失的数字是: %d\n", missingNumber_xor(nums2, size2)); // 应该输出 8
    return 0;
}
/**
 * @brief 使用异或法寻找缺失的数字
 * @param nums 整数数组
 * @param numsSize 数组的大小
 * @return 缺失的数字
 */
int missingNumber_xor(int* nums, int numsSize) {
    int missing = numsSize; // 初始值为 n
    for (int i = 0; i < numsSize; i++) {
        // 利用异或的性质，将所有索引和数组元素进行异或
        missing ^= i ^ nums[i];
    }
    return missing;
}

优缺点

• 优点:
  • 没有整数溢出的风险,因为异或操作不会导致数值变大。
  • 时间复杂度为 O(n)。
  • 空间复杂度为 O(1)。
  • 这是解决此问题的最优方法,在面试中备受青睐。
• 缺点:

  相比求和法，思路稍微不那么直观,需要理解异或的性质。

排序法

这个方法比较直接,但效率不高。

思路

1. 先对数组进行排序。
2. 然后遍历排序后的数组，检查 nums[i] 是否等于 i。
3. nums[i] != i，i 就是缺失的数字。
4. 如果遍历结束都没有找到，说明缺失的数字是 n（即数组的最后一个位置）。

C 语言代码实现

#include <stdio.h>
#include <stdlib.h> // 用于 qsort
// 比较函数，用于 qsort
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
int missingNumber_sort(int* nums, int numsSize);
int main() {
    int nums1[] = {3, 0, 1};
    int size1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("数组: [3, 0, 1]\n");
    printf("缺失的数字是: %d\n", missingNumber_sort(nums1, size1)); // 应该输出 2
    int nums2[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
    int size2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("\n数组: [9, 6, 4, 2, 3, 5, 7, 0, 1]\n");
    printf("缺失的数字是: %d\n", missingNumber_sort(nums2, size2)); // 应该输出 8
    return 0;
}
int missingNumber_sort(int* nums, int numsSize) {
    // 对数组进行排序
    qsort(nums, numsSize, sizeof(int), compare);
    // 遍历数组，查找第一个 nums[i] != i 的位置
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    // 如果所有数字都匹配，说明缺失的是最后一个数字 n
    return numsSize;
}

优缺点

• 优点:

  思路简单,容易实现。

• 缺点:
  • 效率较低，排序的时间复杂度通常是 O(n log n)，这比前两种方法的 O(n) 要慢。
  • 改变了原始数组（如果不想改变，需要创建一个副本，空间复杂度变为 O(n)）。
  • 在面试中，除非题目明确要求,否则通常不会被作为首选方案。

总结与对比

• 在日常练习或面试中，异或法是解决“寻找缺失数字”问题的最佳选择,因为它既高效又安全。
• 数学求和法也是一个非常好的备选方案，在大多数情况下表现优异,只需注意潜在的溢出问题。
• 排序法通常不推荐,除非有特殊的约束条件。