如何在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));
    }
}

需要帮助解决这个问题！

- user2916886

---

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

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

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

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

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

Answer 1

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

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

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

其次，不要试图聪明。使用异或是“聪明”的做法。你不会找到一个简单的使用异或的解决方案。这将是一些纠结、复杂的混乱。保持简单：

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

- John Kugelman

---

谢谢您的解释，但我在将上述伪代码转换为程序方面遇到了麻烦。您能帮忙吗？ - user2916886

@user2916886 你需要什么具体帮助？哪个部分让你困扰？你理解它的概念吗？ - John Kugelman

我理解哈希映射可以为数组中的每个元素及其在数组中出现的次数建立映射。但我无法将第一个for循环（完整的）和第二个for循环的条件转换为代码。 - user2916886

@user2916886 或许你可以发布一个新问题，询问如何将伪代码翻译成实际的Java代码。评论区并不是很适合这个问题。（另外，我现在得离开一会儿，暂时无法帮助你。） - John Kugelman

Answer 2

也许这是一个老帖子，但是这里是我的答案。

在我看来，不需要计算一个数字出现的次数来确定它是奇数还是偶数。我们可以使用像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);
    } 
}

- gipinani

Answer 3

这句话的意思是：“这个得分是100%。”

public int solution(int[] A) {
    Arrays.sort(A);
    for(int i = 0; i < A.length; i = i+2){
        if(i == A.length-1)
        return A[i];

        if (A[i]!=A[i+1])
        return A[i];
    }
    return 0;
}

- Saurabh

Answer 4

这个解决方案在Codility上得分为100％。我们所做的就是初始化一个HashMap。 HashMap的查找时间是O（1）常数时间，请参见此处 了解更多信息。由于我们只循环一次整个数组，因此最终获得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;
    }
}

- Omar Abid

Answer 5

这是我使用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();  

    }

- 0xAliHn

Answer 6

使用 Set 对象，在若该元素 !exist 则增加，否则删除，以此方法在 Codility 上获得了 100% 的得分。

public int solution(int[] A) 
{
    Set<Integer> oddSet = new HashSet<>();
    
    for(int i = 0; i < A.length; i++)
    {
        if(!oddSet.contains(A[i]))
        {
            oddSet.add(A[i]);
        }
        else
        {
            oddSet.remove(A[i]);
        }
    }
    /* Based on the pre-conditions, we are sure that only one 
       remains here that is unique. So we just return that. */
    return oddSet.iterator().next();
}

- jetGeekster

Answer 7

使用Linq在C#中提供了100%的解决方案。很高兴看到Linq足够快。

  public static int solutionOddOccurrencesInArrayLinq(int[] A)
    {
        if (A.Length == 0)
            return 0;

         var result = A
            .GroupBy(e => e)
            .Where(g => g.Count() % 2 == 1)
            .Select(g => g.Key);

        return result.FirstOrDefault();

    }

- Karl Hoaglund

Answer 8

这个解决方案让我在Codility上获得了100%的通过：

  public int solution(int[] A) {

        if (A.length == 0) {
            return 0;
        }
        int num = 0;
        for (int i = 0; i < A.length ; i++) {
            // using XOR function 1. XOR of number with itself = 1 and XOR number with 0 = number itself
            num = num ^ A[i];
        }


        return num;
    }

- Amit Dhawan

Answer 9

使用Kotlin进行编程

fun oddOccurrencesInArray(array: IntArray) {
   
    var count = 0
    var arrayList = mutableListOf<Int>()
    array.sort() //sort the array
    var element = array[0]
    for (j in 1 until array.size) {
        if (element == array[j]) {
            count++
        } else {
            if (count == 0)
                arrayList.add(array[j-1])
            count = 0
            element=array[j]
        }
    }
    if(count==0)
        arrayList.add(array[array.size-1])
    println("Given array: ${array.contentToString()} missing:${arrayList.toString()}")
}

- Mubarak

Answer 10

你不需要真正跟踪每个整数出现的次数，只需要知道它是否出现了奇数次。因此，从一个空的数据结构（map、哈希表、字典等）开始，这正确地反映了你没有看到任何数字出现奇数次的状态。现在对于数组中的每个数字x，如果x在map中，则将其删除（现在你已经看到它偶数次），否则添加它。

- gurubelli