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

Question

我遇到了以下问题：

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

我的想法是：

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

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

你认为还有其他方法吗？如果没有，那么这两种方法中哪一种更好？

提前感谢！

- Vikram

Answer 1

你可以修改第一种方法，使用哈希集合而不是哈希图。

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

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

由于在哈希集合中访问元素是O(1)，所以这个算法具有O(N)时间复杂度。

- Sergey Kalinichenko

---

谢谢你的回答。但是，为什么要使用 HashSet 而不是 HashMap？HashSet 避免重复元素的优势对我们来说并没有太大帮助，因为我们无论如何都要搜索该元素，如果找到了就会删除，否则就添加。 - Vikram

@Vikram，使用HashMap可以存储显式计数。在Java中，这意味着存储一个包装整数，你只需要它的最后一位（决定它是偶数还是奇数），而且你将要丢弃它。在其他语言中，当你只需要一个比特位时，仍然会存储完整的整数，这是浪费的。 - Sergey Kalinichenko

这个答案展示了为什么这个人有20万分...做得好。 - Tom Swifty

如果发生冲突怎么办，哈希集合的访问时间复杂度不就不是O(1)了吗？ - committedandroider

你能详细说明一下吗？是什么导致所有操作平均化？ - committedandroider

Answer 2

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

你选择哪种解决方案取决于你是否能承担额外的内存。

- Jim Mischel

---

是的...你说得有道理！如果我们选择排序，数组将被修改。 - Vikram

Answer 3

在Java中查找数组中出现奇数次的数字

package yourPackageNameGoesHere;

import java.util.*;

public class FindTheNumberOccurringOddNumberOfTimesInArray {
public static void main(String[] args) {
    int array [] = {20, 40, 50, 50, 20, 30, 30, 50, 20,20};
    findTheNumberOccurringOddNumberOfTimesInArray(array);
}

public static void findTheNumberOccurringOddNumberOfTimesInArray(int arr[]) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int num : arr) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    for (int n : map.keySet()) {
        if (map.get(n) % 2 == 1) {
            System.out.println(n + " is occurring " + map.get(n) + " time(s).");
        }
    }
}

}

- Bayram Binbir

Answer 4

基本上，这可以作为一种重新平衡效率的练习来完成：您遍历数字列表，并对于您已经拥有的每个数字，您都会将其删除。这样，您的比较集合大约是可能最大值的一半大小。当然，这并不改变O（n lg n），并且您在每个步骤中进行分配/取消分配，这可能会更加昂贵。

因此，使用混合策略可能很有趣：快速排序非常快，但您基本上希望在两个条目相等且至少有（n-1）/ 2个条目相等时将它们合并。快速排序实际上无法在排序时容纳元素的删除。

因此，使用基于数组的方法（以减少分配成本），我更愿意使用一些基于堆的方法。每当您遇到相等的元素时，您就会删除一个元素。堆排序与快速排序相当竞争，并且能够提前修剪树将会非常有用。

- user4453251