java 程序查找数组中出现奇数次的数字。

Question

给你一个整数数组。除一次外，所有数字出现偶数次。您需要找到出现奇数次的数字。你需要用 o(n) 时间复杂度和 o(1) 空间复杂度来解决它。
例如：

int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
Number which occurs odd number of times is : 50

Answer 1

解决方案 1：使用两个 for 循环并比较元素：
这是这个问题的蛮力解决方案，但它需要 o(n*n) 时间复杂度。

解决方案 2：使用Hashing

您可以将 key 用作数字并将 count 用作值，每当 key 重复时，您都可以将 counter 增加 1。

int getOddTimesElementHashing(int ar[]) 
{
    int i;

    HashMap<Integer,Integer> elements=new HashMap<Integer,Integer>();
    for (i = 0; i < ar.length; i++) 
    {
        int element=ar[i];
        if(elements.get(element)==null)
        {
            elements.put(element, 1);

        }
        else
            elements.put(element, elements.get(element)+1);
    }
    for (Entry<Integer,Integer> entry:elements.entrySet()) { 
        if(entry.getValue()%2==1)
        {
            return entry.getKey();
        }

    } 
    return -1;
}

但上述解决方案需要 o(n) 的空间复杂度。

方案三：使用bitwise XO：
您可以对所有元素进行: bitwise XO，它将为您提供最终出现奇数次的元素。

  int getOddTimesElement(int ar[]) 
  {
      int i;
      int result = 0;
      for (i = 0; i < ar.length; i++) 
      {
       result = result ^ ar[i];
      }
      return result;
  }

上述算法解决了时间复杂度为 O(n) 和空间复杂度为 o(1) 的问题，这是上述程序的最佳解决方案。

查找数组中出现奇数次的数字的Java程序：

package org.arpit.java2blog;

//Java program to find the element occurring odd number of times

public class NumberOddTimesMain 
{
    int getOddTimesElement(int ar[]) 
    {
        int i;
        int result = 0;
        for (i = 0; i < ar.length; i++) 
        {
            // XOR operation
            result = result ^ ar[i];
        }
        return result;
    }

    public static void main(String[] args) 
    {
        NumberOddTimesMain occur = new NumberOddTimesMain();
        int array[] = new int[]{20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20};
        System.out.println("Number which occurs odd number of times is : "+occur.getOddTimesElement(array));
    }
}

当你运行上面的程序时，你会得到以下输出：

Number which occurs odd number of times is : 50