查找数组唯一元素：奇数长度数组输出错误，偶数长度正常

问题说明 #

需求是找出数组中唯一不重复的元素（其余元素均成对重复），但现有代码存在逻辑错误：

• 当数组长度为奇数时，会误将重复元素识别为唯一元素（例如输入长度9的数组[1,1,2,2,3,3,4,4,5]，代码输出1 is unique，正确结果应为5）
• 数组长度为偶数时运行正常

用户提供的代码 #

#include<stdio.h>
#include<stdbool.h>
int main()
{
    int n;
    printf("Enter number for array: \n");
    scanf("%d", &n);
    int a[n];
    printf("Enter array: \n");
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        for (int j = i + 1; j < n; j++)
        {
            if(a[i]==a[j]){
                flag = true;
            }
        }
        if(flag==false){
            printf("%d is unique", a[i]);    /* should be 5 here */
            break;
        }
    }
    return 0;
}

错误运行输出 #

Enter number for array: 
9 
Enter array: 
1
1
2
2
3
3
4
4
5
1 is unique

错误原因 #

代码的核心逻辑漏洞在于：只检查当前元素之后的元素是否重复，完全忽略了当前元素之前的元素。以测试用例为例：
当循环到i=1（数组第二个元素，值为1）时，内层循环从j=2开始遍历，后面没有其他1，因此flag保持为false，代码错误地判定该元素为唯一元素并输出，随后终止循环，根本不会遍历到真正的唯一元素5。

修复方案 #

方案1：遍历整个数组检查重复（直观易懂） #

修改内层循环，遍历整个数组并跳过当前元素自身，只要找到任意一个重复项就标记为非唯一：

#include<stdio.h>
#include<stdbool.h>
int main()
{
    int n;
    printf("Enter number for array: \n");
    scanf("%d", &n);
    int a[n];
    printf("Enter array: \n");
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++)
    {
        bool is_unique = true;
        // 遍历整个数组，跳过自身
        for (int j = 0; j < n; j++)
        {
            if(i != j && a[i] == a[j]){
                is_unique = false;
                break; // 找到重复项就提前退出，提升效率
            }
        }
        if(is_unique){
            printf("%d is unique", a[i]);
            break;
        }
    }
    return 0;
}

方案2：使用异或运算（高效最优） #

利用异或运算的特性（自身异或为0，0异或任何数为自身，满足交换律），将所有元素依次异或，最终结果就是唯一不重复的元素，时间复杂度O(n)，空间复杂度O(1)：

#include<stdio.h>
int main()
{
    int n;
    printf("Enter number for array: \n");
    scanf("%d", &n);
    int a[n];
    printf("Enter array: \n");
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    int unique = a[0];
    for (int i = 1; i < n; i++)
    {
        unique ^= a[i];
    }
    printf("%d is unique", unique);
    return 0;
}

内容的提问来源于stack exchange，提问作者ayushggg74