问题描述
小U是一名勇敢的守卫，负责保护村庄的魔法水晶。每个水晶都有一个能量值，邪恶的巫师施法让所有水晶的能量值都成对出现，只有一颗特殊的水晶能量值是独一无二的，它能够破除巫师的诅咒。小U需要快速找出这颗特殊水晶的能量值，才能激活防御法阵。
要求：
- 设计一个算法，在 O(n) 时间复杂度内找出唯一不重复的能量值。
- 尽量使用最少的额外空间，以应对紧急情况下的资源限制。
测试样例
样例1：
输入：
crystals = [5, 3, 5, 2, 3, 1, 1]输出：2解释：能量值 2 只出现一次，是破除诅咒的关键水晶。
样例2：
输入：
crystals = [10, 20, 10, 30, 20, 40, 40]输出：30解释：30 是唯一不重复的能量值，对应着那颗特殊的水晶。
样例3：
输入：
crystals = [100, 200, 300, 100, 200, 300, 500]输出：500解释：500 是独一无二的能量值，小U必须尽快找到它。
约束条件
- 1 ≤ crystals.length ≤ 1001
- 0 ≤ crystals[i] ≤ 1000
- 水晶数量为奇数
- 除了一个能量值只出现一次外，其余每个能量值都恰好出现两次
程序代码
#include <stdio.h>
int findUnique(int* crystals, int crystalsSize) {
int result = 0;
for (int i = 0; i < crystalsSize; i++) {
result ^= crystals[i];
}
return result;
}
int main() {
int crystals1[] = {5, 3, 5, 2, 3, 1, 1};
int crystals2[] = {10, 20, 10, 30, 20, 40, 40};
int crystals3[] = {100, 200, 300, 100, 200, 300, 500};
printf("%d\n", findUnique(crystals1, 7)); // 2
printf("%d\n", findUnique(crystals2, 7)); // 30
printf("%d\n", findUnique(crystals3, 7)); // 500
return 0;
}
#include <stdio.h>
int findUnique(int* crystals, int crystalsSize) {
int result = 0;
for (int i = 0; i < crystalsSize; i++) {
result ^= crystals[i];
}
return result;
}
int main() {
int crystals1[] = {5, 3, 5, 2, 3, 1, 1};
int crystals2[] = {10, 20, 10, 30, 20, 40, 40};
int crystals3[] = {100, 200, 300, 100, 200, 300, 500};
printf("%d\n", findUnique(crystals1, 7)); // 2
printf("%d\n", findUnique(crystals2, 7)); // 30
printf("%d\n", findUnique(crystals3, 7)); // 500
return 0;
}
运行结果
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/u013741272/article/details/166789781
