java - 给定 +ve 个整数数组，找出在 O(n) 时间和常数空间中出现奇数次的数字。

Question

给定一个正整数数组。除一个数字出现奇数次外，所有数字都出现偶数次。在 O(n) 时间和常数空间中找到数字。

int getOddOccurrence ( int ar[]){
    int i;
    int res = 0;
    for (i = 0; i < ar.size; i++)
        res = res ^ ar[i];
    return res;
}

/* Diver function to test above function */
PSVM() {
    int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
    SOP(getOddOccurrence(ar));
}

方法一:对数组中的所有元素进行异或运算

我正在尝试 x-or 所有元素。那是
正确的做法？上面是使用异或的代码

方法 2:通过使用 HashMap如果我使用 hashmap ，空间复杂度将为 O(n)。这不好。

我应该使用哪种方法？

Answer 1

这个问题假设只有一个数出现奇数次
数组中的次数。如果你有更多这样的数字 - 说其中的 K 个:a1, a2, ... aK ,
然后在循环结束时，在 res 中你会得到这个值。

res == a1 ^ a2 ^ ... ^ aK

根据该值您无法推断/提取所有 K 个未知数 a1, a2, ... aK .

Buf ... 你看，如果 K=1(即如果你恰好有一个数字出现
奇数次)，最后你会得到 res只是那个数字。

只要您了解其工作原理，就可以使用第一种方法。

此外，在第二种方法中，空间不是 O(n)但是O(s) ,
其中 s是数组中不同值的计数。和你一样
只有 1 个数字出现奇数次我们可以肯定地说
那2*s + 1 <= n即 s <= (n-1)/2 .所以空间复杂度
是O((n-1)/2)在第二种方法中。当你的数组
看起来像这样:s数字出现两次，1数出现一次。