algorithm - 给定一个整数数组，其中一些数字重复 1 次或 2 次，但有一个数字重复 3 次，你如何找到它？

Question

给定一个整数数组，其中一些数字重复 1 次，一些数字重复 2 次，只有一个数字重复 3 次，你如何找到重复 3 次的数字。不允许使用哈希。算法的复杂度应该是O(n)

Answer 1

我假设数组没有排序，或者类似地，一个数字的重复不会出现在一个连续的运行中。否则，问题真的很微不足道:只需使用大小为 3 的窗口扫描数组一次，如果该窗口中的每个数字都相同，那么这就是在一次连续运行中重复 3 次的数字。

如果重复是分散的，那么问题就变得更有趣了。

因为这是作业，所以我只会给你一个提示。

这个问题与给定一个未排序整数数组的问题类似，所有数字出现偶数次，除了一个出现奇数次。

通过对数组中的所有数字执行异或操作，可以很容易地在 O(N) 中找到该数字；结果是出现奇数次的数字。

之所以可行，是因为 x xor x = 0。

例如，3 xor 4 xor 7 xor 0 xor 4 xor 0 xor 3 = 7。