查找数组中未出现两次的整数

我试图解决这个问题:在一个整数数组中,所有数字恰好出现两次,除了一个恰好出现一次的数字。

一个简单的解决方案是对数组进行排序,然后测试非重复。 但我正在寻找具有时间复杂度O(n)的更好的解决方案。

您可以对整个arrays使用“xor”操作。 每对数字将相互抵消,为您留下所寻求的价值。

int get_orphan(int const * a, int len) { int value = 0; for (int i = 0; i < len; ++i) value ^= a[i]; // `value` now contains the number that occurred odd number of times. // Retrieve its index in the array. for (int i = 0; i < len; ++i) { if (a[i] == value) return i; } return -1; }