arrays - 查找数组中出现奇数次的所有元素

Question

我遇到了以下问题:

'找出数组中出现奇数次的所有元素'。

我对此的看法是:

1. 使用HashMap:将数组中的值添加为HashMap 中的键。每个键对应的值将是遇到该键的次数。

2. 在 O(N log N) 中使用快速排序对数组进行排序，然后遍历数组以检查哪些元素出现奇数次。

您怎么看，还有其他方法吗？如果不是，那么这两种方法中哪种更好？

提前致谢!

Answer 1

您可以修改您的第一种方法以使用哈希集而不是 HashMap 。

创建一个最初为空的哈希集。遍历数组的元素。对于每个元素，检查哈希集合:如果当前数组元素不在集合中，则添加它；否则，将其删除。

当您到达数组的末尾时，您的哈希集将包含在您的数组中出现奇数次的每个对象。

由于访问哈希集中的元素是 O(1)，因此该算法具有 O(N) 时间复杂度。