这种贪婪的方法是什么？

Question

我们有一个n数字数组,除了一个数字之外,所有数字都在这个数组中重复了很多次; 我们想要找到重复奇数次的数字.

我认为最优算法比时间复杂度更好,O( n Log(n) )因为我们可以对数组进行排序然后迭代它,当我们看到一个新数字时,我们增加一个累加器,当我们再次看到它时,我们减少累加器,最后每个成员的累加器不是零已经重复奇数次.

此外,我认为它没有一个更好的算法,O(n)因为如果它已经必须是O( Log(n) ),为此我们需要一个排序的数组,但我们的初始数组不是.

Answer 1

如果数字是整数,则可以只计算数组中的所有值.结果是重复奇数次的数字(这是正确的,因为x xor x = 0任何x).这种算法的复杂性显而易见O(n).