C语言/数据结构算法题：异或运算找出唯一出现一次的数字（O(n)时间+O(1)空间）

问题描述在一个班级中每位同学都拿到了一张卡片上面有一个整数。有趣的是除了一个数字之外所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上的数字是什么。要求设计一个算法使其时间复杂度为 O(n)其中 n 是班级的人数。尽量减少额外空间的使用以体现你的算法优化能力。约束条件1 ≤ cards.length ≤ 10010 ≤ cards[i] ≤ 1000班级人数为奇数除了一个数字卡片只出现一次外其余每个数字卡片都恰好出现两次代码如下#include stdio.hint findUnique(int* cards, int cardsSize) {int result 0;for (int i 0; i cardsSize; i) {result ^ cards[i];// 异或操作相同为0不同为1}return result;}int main() {int cards1[] {1, 1, 2, 2, 3, 3, 4, 5, 5};int cards2[] {0, 1, 0, 1, 2};int cards3[] {7, 3, 3, 7, 10};printf(%d\n, findUnique(cards1, 9));printf(%d\n, findUnique(cards2, 5));printf(%d\n, findUnique(cards3, 5));return 0;}运行结果解题思路核心思想异或运算XOR异或运算的性质交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)自反性a ^ a 0恒等性a ^ 0 a执行过程对于数组{1, 1, 2, 2, 3, 3, 4, 5, 5}步骤当前值result异或运算初始—0—1110 ^ 1 12101 ^ 1 03220 ^ 2 24202 ^ 2 05330 ^ 3 36303 ^ 3 07440 ^ 4 48514 ^ 5 19541 ^ 5 4结果 4✅复杂度分析指标值时间复杂度O(n) — 只需遍历一次数组空间复杂度O(1) — 只使用一个整数变量result关键规律异或就是“无进位加法”XOR异或在二进制中的本质是按位相加但不进位。