我正在尝试查找数组中出现奇数次的所有元素。我做了一点工作，但是如果只有一个数字出现奇数次，我的代码只会返回正确的答案。如果有两个或两个以上出现的奇数，我无法处理。我的理解是，如果我们对元素进行按位异或，就会得到一个奇数发生的元素。如何改善多个数字？
下面是我的代码：
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));
}
}
需要帮助解决此问题！
public int oddoccurence(int[] arr, int size);
首先，可以有多个数字出现奇数次。如果仅返回单个int，则无法编写此函数并使之起作用。您需要一个可以返回多个数字的函数。
public int[] oddOccurrences(int[] array);
第二，不要试图变得聪明。使用XOR是“明智的”。您将不会找到使用XOR的简单解决方案。这将是令人费解的，复杂的混乱。保持简单：
示例伪代码：
// 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);
}
}
[也许是一个旧帖子。
我认为没有必要计算数字的出现来确定它是否为奇数。让我们使用类似Set的数据结构，如果尚不存在，则将其添加到该结构中；如果已经存在，则将其删除。
类似这样的东西：
public int solution(int[] A){
Set<Integer> unpaired = new HashSet<Integer>();
for (int i = 0; i<A.length; i++){
if (unpaired.contains(A[i])){
unpaired.remove(new Integer(A[i]));
}else{
unpaired.add(A[i]);
}
}
// all printed out values are odd
for (Integer res : unpaired){
System.out.println(res);
}
}
您真的不需要跟踪您看到每个整数的次数，而只需跟踪是否看到奇数次即可。因此，从您的数据结构（映射，哈希表，字典等）为空开始，它可以正确地反映您看到奇数次没有数字的状态。现在，对于数组中的每个数字x，如果x在映射中，则将其删除（现在您已经看过偶数次了，否则将其添加）
这是我使用HashMap的解决方案：
public int solution(int[] A) {
HashMap<Integer, Integer> map = new HashMap<>();
HashSet<Integer> val = new HashSet<>();
for (int i=0; i<A.length; i++){
if (map.get(A[i]) == null) {
map.put(A[i], 1);
} else map.put(A[i], map.get(A[i])+1);
if (map.get(A[i])%2 == 1)
val.add(A[i]);
else val.remove(A[i]);
}
Iterator<Integer> itr = val.iterator();
return itr.next();
}
此解决方案的可编码性得分为100％。我们要做的只是简单地初始化一个HashMap。 HashMap的查找时间为O（1）恒定时间，请参见here for more info。由于我们仅循环遍历整个数组一次，所以我们以O（N）时间结束，其中N是数组的长度。
如果HashMap中已经存在一个元素，则可以将其删除，因为我们已经找到了它的对应对。到此为止，我们应该以只有一对对的HashMap结尾。只需输出此数字即可完成。
import java.util.*;
class Solution {
public int solution(int[] A) {
int key;
Map<Integer, Integer> unpaired = new HashMap<Integer, Integer>();
for (int i = 0; i < A.length; i++){
key = A[i];
Integer value = unpaired.get(key);
if (value != null){
unpaired.remove(key); // Remove by key
}
else{
unpaired.put(key,0);
}
}
for (Map.Entry<Integer, Integer> entry : unpaired.entrySet())
{
key = entry.getKey();
}
return key;
}
}
我认为使用Map存储出现的次数是解决此问题的正确方法，但是如果不同的次数太多，则需要更多的内存，使用BitMap也可以实现并且需要更少的内存。] >
public static List<Integer> oddNumbers(int[] array, int size) { BitSet bitSet = new BitSet(); for (int i = 0; i < size; i++) { bitSet.flip(array[i]); } List<Integer> resp = new ArrayList<>(); for (int i = 0; i < bitSet.length(); i++) { if (bitSet.get(i)) { resp.add(i); } } return resp; }测试用例是：
@Test
public void test_oddNumbers() throws Exception {
int[] arr = {2, 5, 5, 2, 2, 3, 3, 3, 1, 7, 8, 9, 9, 9};
List<Integer> resp = oddNumbers(arr, arr.length);
assertTrue(resp.size() == 6);
assertTrue(resp.containsAll(Arrays.asList(1, 2, 3, 7, 8, 9)));
}
//此解决方案的可编码性得分为100％。
问题非常简单，只需对数组的所有元素使用按位异或。原因是只有一个元素是未配对的。