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

Question

我遇到了以下问题：

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

我对此的想法是：

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

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

你怎么看，有没有其他方法可以解决这个问题？如果不是，那么这两种方法中哪一种更好？

提前致谢！

Answer 1

您可以修改您的第一种方法以使用散列集而不是散列映射。

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

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

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

Answer 2

“更好”取决于上下文。使用散列映射或散列集会更快，并且具有不修改原始数组的优点，但它需要 O(N) 额外的内存。排序和计数需要更长的时间并修改数组，但不需要额外的内存。

您选择哪种解决方案取决于您是否负担得起额外的内存。

Answer 3

基本上，这可以作为一种重新平衡效率的练习来完成：你检查你的数字列表，对于你已经拥有的每个数字，你再次删除它。这样，您的比较集大约是可能最大值的一半。当然，这不会改变 O(n lg n)，并且您在每一步都会得到一个分配/解除分配，这可能会更加昂贵。

所以使用混合策略可能会很有趣：快速排序非常快，但您基本上希望在两个条目相等时合并它们，并且至少 (n-1)/2 个条目相等。快速排序并不能真正适应排序时元素的删除。

因此，对于基于数组的方法（以减少分配成本），我宁愿使用一些基于堆的方法。每当你遇到相同的元素时，你就移除一个。堆排序与快速排序相比具有相当的竞争力，并且能够提前修剪树将会很有帮助。