求数组中唯一出现一次的元素（满足O(n)等约束，禁用XOR）

我明白你卡在这里很久的感觉——既要线性时间、不能用哈希表，还只能用基础的算术和比较操作，连常规XOR都因为位数问题不能用，确实头疼。不过咱们可以换个思路，利用数组元素位数的特性来设计方案：

解法思路：基于计数数组的线性时间方案 #

既然题目里提到数组中每个数字的位数约为O(log(n))，这意味着元素的取值范围是O(n)（因为位数为log(n)的数，最大值大概是2^log(n)=n量级）。基于这个前提，我们可以用计数数组来实现线性时间的统计，完全符合你的约束：

• 首先遍历一次数组，找到元素的最大值max_num（只用比较操作就能完成）。
• 创建一个大小为max_num + 1的计数数组，初始值全为0（这里用加法操作初始化）。
• 再次遍历原数组，对每个元素num，执行count[num] += 1（仅用加法）。
• 最后遍历计数数组，找到第一个值为1的索引，这个索引就是那个仅出现一次的元素x（只用比较操作）。

为什么符合所有约束？ #

• 线性时间复杂度：三次遍历都是O(n)级别的（因为max_num是O(n)，所以第三次遍历也是O(n)），总时间是O(n)。
• 不使用哈希表：计数数组是连续的线性存储空间，不属于哈希表结构，完全符合要求。
• 仅用比较与加减乘除：整个过程只用到了比较（找最大值、判断计数是否为1）和加法（计数累加、初始化），没有用到任何位运算或哈希相关操作。

补充：纯数学思路的局限 #

如果你不想用额外空间，尝试纯数学推导的话，会遇到瓶颈：假设重复元素的和为S，平方和为Q，唯一元素为x，数组总和为sum_total，数组元素的平方和为sum_squares，我们能得到两个方程：

• sum_total = 2*S + x
• sum_squares = 2*Q + x²

但这两个方程里有三个未知量（S、Q、x），无法直接解出x，除非有额外的元素范围信息，所以这个思路无法落地。

综上，计数数组的方案是最直接且完全满足所有约束的解法。

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