C语言利用异或运算求无序数组缺失数字

纸上星河

发布时间：2026-10-15| 1人浏览过

原创

在处理包含连续整数但缺失一个数字的无序数组时，传统方法往往依赖排序或哈希表，导致时间或空间复杂度过高。本文将展示如何利用位运算中的异或（XOR）特性，在O(N)时间复杂度和O(1)额外空间内精确找到缺失数字，避免创建完整副本或修改原数组。

异或运算的核心特性

解决此问题的关键在于理解按位异或（^）的两个数学性质：

自反性：任何数与自身异或结果为 0，即 a ^ a = 0。
交换律与结合律：异或运算的顺序不影响最终结果，即 a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b。

这意味着，如果我们把一组数中的每一个数都进行一次异或操作，成对出现的数字会相互抵消为 0，最终剩下的结果就是那个只出现一次的数字。

正如图片所示，3 与 3 异或的结果为 0。这一特性为我们提供了一种“抵消”重复元素的极简思路。

算法逻辑推导

假设我们有一个长度为 N 的无序数组，它本应包含从最小值 min 开始的 N+1 个连续整数，但缺失了其中一个。我们的目标是找出这个缺失的数字。

直观上，我们可以创建一个完整的序列（包含所有连续数字），然后将原始数组与完整序列混合进行异或。因为除了缺失数字外，其他所有数字在两个集合中都出现了一次，异或后都会变为 0，仅剩缺失数字留存。

如图所示，如果我们将原始数组 {1, 2, 3, 5} 与完整数组 {1, 2, 3, 4, 5} 混合，除了 4 之外，其他数字均成对出现。通过对整个混合序列执行异或，最终结果即为 4。

第1步：分析代码实现策略

虽然理论上可以将两个数组拼接，但这需要额外的内存。更优的做法是在一次遍历中，分别对原始数组元素和目标序列元素进行累积异或。由于异或满足交换律，无需关心元素的相对位置，乱序数组同样适用此方法。

如图示例，即使数组是乱序的，只要保证每个非缺失数字都参与了两次异或（一次来自原数组，一次来自目标序列），它们就能被完全抵消。

C语言代码实现

以下代码演示了如何不创建新数组，仅通过遍历一次原始数组和一次生成目标序列来完成计算。

#include <stdio.h>

int find_missing_number(int arr[], int len);

int main() 
{
    // 测试用例：连续数组缺少一个数字
    int arr[] = {78, 79, 81, 83, 82, 84};
    int len = sizeof(arr) / sizeof(arr[0]);
    
    int res = find_missing_number(arr, len);
    printf("Missing number is: %d\n", res);
    return 0;
}

int find_missing_number(int arr[], int len)
{
    int min = arr[0];
    int temp1 = 0; // 用于存储目标完整序列的异或结果
    int temp2 = 0; // 用于存储原始数组的异或结果
    
    // 第一步：找到数组中的最小值，以确定完整序列的起始点
    for (int i = 0; i < len; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    
    // 第二步：计算完整序列 (min 到 min + len) 的异或值
    // 注意：完整序列长度为 len + 1
    for (int j = min; j <= min + len; j++)
    {
        temp1 ^= j;
    }
    
    // 第三步：计算原始数组所有元素的异或值
    for (int i = 0; i < len; i++)
    {
        temp2 ^= arr[i];
    }
    
    // 第四步：将两者异或，相同元素抵消，剩余即为缺失数字
    return temp1 ^ temp2;
}