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

Question

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

5

我尝试查找在一个数组中出现奇数次的所有元素。我已经做了一些工作，但是我的代码只有在只有一个数字出现奇数次时才返回正确答案。如果有两个或更多的奇数出现数字，那么我就无法处理它。我理解的是，如果我们对元素进行按位异或，那么我们会得到一个奇数出现的元素。如何改进它以处理多个数字？

以下是我的代码：

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));
    }
}

需要帮助解决这个问题！

- user2916886

1

这个代码：res = res ^ arr[i]; 怎么能帮助你找出奇数呢？想一想偶数的特性... - pedromss

我读到过，要找到一个奇数，只需要对所有数字进行按位异或运算。我想知道是否可以修改这个属性来查找所有的奇数。 - user2916886

一个 Map<Integer, Integer> 对于解决这个问题会更容易吗？ - Kent

如果我使用只有一个在数组中出现了奇数次的数字来运行上述程序，它会返回正确的答案。 - user2916886

@pedromss 我想在一个数组中找到出现奇数次的数字，而不仅仅是奇数。 - user2916886

显示剩余4条评论

15个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mishoo78 · Answer 1

问题非常简单，只需对数组的所有元素使用按位异或。原因是只有一个元素是未配对的。

- TongChen · Answer 2

我认为使用 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)));
}

- Ramesh J · Answer 3

//这个解决方案在Codility上得分100%。

import java.util.Arrays;

class Solution {

public int solution(int[] A) {
    // write your code in Java SE 8

    Arrays.sort(A);

    int length = A.length;

    for (int i = 0, j = 1; i < length; i++) {
        if (j < length && A[i] == A[j]) {
            i++;
            j = j + 2;
        } else {
            return A[i];
        }
    }

    return 0;   
}

}

- Leandro Maro · Answer 4

 private static int Odd(int[] a) {
        int unpaired;
        unpaired = a[0];

        for(int i = 1; i< a.length; i++){
            unpaired = unpaired ^ a[i]; // xor
        }

        return unpaired;
    }

- Ashwathama · Answer 5

public class GetOddOccurenceInArray {
    
    public static ArrayList<Integer> getOddOccurence(int arr[]){
        
        int count = 0;
        ArrayList<Integer> result = new ArrayList<>(); 
        HashMap<Integer, Integer> hmap = new HashMap();

        for(int num : arr){
            if(hmap.get(num) == null){
                hmap.put(num, count+1); 
            }
            else
                hmap.put(num, hmap.get(num)+1);
        }
          
        for (Entry<Integer,Integer> entry : hmap.entrySet()) { 
            if(entry.getValue()%2==1){
                //System.out.println("number is "+entry.getKey());               
                result.add(entry.getKey());
            }

        }

        return result;      
    }
    
    public static void main(String[] args){
        int arr[] = {1,2,2,2,3,3,3,3,4,5,6,6,7,8};
        ArrayList<Integer> occurred = getOddOccurence(arr);
        System.out.println("numbers occurred odd times : "+ occurred.toString());   
    }
}