java - Java 如何查找数组中所有奇数出现的元素

Question

我试图找到数组中出现奇数次的所有元素。我算了一点，但如果只有一个数字出现奇数次，我的代码只会返回正确答案。如果有两个或更多奇数出现，我将无法处理它。我的理解是，如果我们对元素进行按位异或，我们会得到一个奇数出现的元素。我如何针对多个数字改进它？

下面是我的代码:

public class OddOccur {
    public int oddoccurence(int[] arr, int size) {
        int res = 0;
        int[] fin = new int[size];

        for (int i = 0; i < size; i++) {
            res = res ^ arr[i];

        }
        return res;
    }

    public static void main(String args[]) {
        int[] arr = { 2, 5, 5, 2, 2, 3, 3, 3 };

        int n = arr.length;
        OddOccur obj = new OddOccur();

        System.out.println("odd occuring element is:"
                + obj.oddoccurence(arr, n));
    }
}

需要帮助来解决这个问题!

Answer 1

public int oddoccurence(int[] arr, int size);

首先，可以有多个数字出现奇数次。如果此函数仅返回一个 int，则无法编写此函数并使其正常工作。您需要一个可以返回多个数字的函数。

public int[] oddOccurrences(int[] array);

其次，不要自作聪明。使用 XOR 是“聪明的”。您不会找到使用 XOR 的简单解决方案。这将是一些错综复杂的困惑。保持简单:

1. 计算每个数字出现的次数。
2. 然后找出所有奇数。

示例伪代码:

// Map from numbers to counts. Assume the counts start at 0.
Map<Integer, Integer> counts;

for (number in array) {
    counts[number] += 1
}

// List of numbers that occur an odd number of items.
List<Integer> oddNumbers;

for (number, count in counts) {
    if (count % 2 != 0) {
        oddNumbers.add(number);
    }
}