出现奇数次的数字

回想一下你在“XOR 运算符”课中解决的挑战，当时我们用到了 XOR 的性质。本课要解决的问题与那个挑战非常相似。我们要探讨的问题是：

找出给定数组中出现奇数次的元素。

你会得到一个包含一些整数元素的数组。其中，除了一个元素以外，其他所有元素出现的次数都是偶数。

假设我们有一个数组 int Arr[11] = { 2, 5, 6, 6, 6, 4, 5, 2, 5, 4, 5}.

在这个数组中：

• “2”出现了两次（偶数）。
• “5”出现了四次（偶数）。
• “6”出现了三次（奇数）。
• “4”出现了两次（偶数）。

所以，这里出现奇数次的是数字“6”。这就是题目要求我们找出的数组中出现奇数次的数字。

正如我们在“XOR”运算符课中看到的，对于一个数字“x”：

• x ⊕ x = 0 （其中“⊕”符号表示 XOR 运算）
• x ⊕ 0 = x

因此，利用第一个性质，所有出现偶数次的元素进行 XOR 运算后都会得到 0；再利用第二个性质，最后剩下的就是出现奇数次的数字。

也就是说，对数组中的所有元素进行 XOR 运算，最终就能得到结果。就是这样，这就是问题的答案。很简单，对吧？

这个问题的时间复杂度是 O(n)，因为我们必须遍历整个数组，并对其中的所有元素进行 XOR 运算。