# 如何找出在未排序数组中出现奇数的两个数字？

2021年3月18日15:35:06 发表评论 735 次浏览

## 本文概述

``````Input: {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45

Input: {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100}
Output: 100 and 5000

Input: {10, 20}
Output: 10 and 20``````

## 推荐：请在"实践首先, 在继续解决方案之前。

O(n)时间和O(1)额外空间解决方案：

。由于XOR运算的以下特性, 所有元素的XOR使我们对x和y进行XOR。

1)任何数字n与自身的XOR等于0, 即n ^ n = 0

2)任意数字n与0的XOR运算得到n, 即n ^ 0 = n

3)XOR是累积和关联的。

。 x和y将进入不同的组。在下面的代码中, 选择xor2的最右边设置位是因为它很容易获得数字的最右边设置位。如果对数组中所有具有相应位(或1)的元素进行XOR, 则将得到第一个奇数。而且, 如果我们对所有具有对应位0的元素进行XOR, 那么我们将获得另一个奇数发生数。由于XOR具有相同的属性, 因此此步骤有效。一个数字的所有出现都将进入同一集合。对所有出现的偶数次出现的所有数字进行XOR运算, 其结果将为0。集合的异或将是奇数发生的元素之一。

## C ++

``````// C++ Program to find the two odd occurring elements
#include <bits/stdc++.h>
using namespace std;

/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times. */
void printTwoOdd( int arr[], int size)
{
int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */
int set_bit_no; /* Will have only single set bit of xor2 */
int i;
int n = size - 2;
int x = 0, y = 0;

/* Get the xor of all elements in arr[]. The xor will basically
be xor of two odd occurring elements */
for (i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];

/* Get one set bit in the xor2. We get rightmost set bit
in the following line as it is easy to get */
set_bit_no = xor2 & ~(xor2-1);

/* Now divide elements in two sets:
1) The elements having the corresponding bit as 1.
2) The elements having the corresponding bit as 0. */
for (i = 0; i < size; i++)
{
/* XOR of first set is finally going to hold one odd
occurring number x */
if (arr[i] & set_bit_no)
x = x ^ arr[i];

/* XOR of second set is finally going to hold the other
odd occurring number y */
else
y = y ^ arr[i];
}

cout << "The two ODD elements are " << x << " & " << y;
}

/* Driver code */
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = sizeof (arr)/ sizeof (arr[0]);
printTwoOdd(arr, arr_size);
return 0;
}

// This is code is contributed by rathbhupendra``````

## C

``````// Program to find the two odd occurring elements
#include<stdio.h>

/* Prints two numbers that occur odd number of times. The
function assumes that the array size is at least 2 and
there are exactly two numbers occurring odd number of times. */
void printTwoOdd( int arr[], int size)
{
int xor2 = arr[0]; /* Will hold XOR of two odd occurring elements */
int set_bit_no;  /* Will have only single set bit of xor2 */
int i;
int n = size - 2;
int x = 0, y = 0;

/* Get the xor of all elements in arr[]. The xor will basically
be xor of two odd occurring elements */
for (i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];

/* Get one set bit in the xor2. We get rightmost set bit
in the following line as it is easy to get */
set_bit_no = xor2 & ~(xor2-1);

/* Now divide elements in two sets:
1) The elements having the corresponding bit as 1.
2) The elements having the corresponding bit as 0.  */
for (i = 0; i < size; i++)
{
/* XOR of first set is finally going to hold one odd
occurring number x */
if (arr[i] & set_bit_no)
x = x ^ arr[i];

/* XOR of second set is finally going to hold the other
odd occurring number y */
else
y = y ^ arr[i];
}

printf ( "\n The two ODD elements are %d & %d " , x, y);
}

/* Driver program to test above function */
int main()
{
int arr[] = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = sizeof (arr)/ sizeof (arr[0]);
printTwoOdd(arr, arr_size);
getchar ();
return 0;
}``````

## Java

``````// Java program to find two odd
// occurring elements

import java.util.*;

class Main
{

/* Prints two numbers that occur odd
number of times. The function assumes
that the array size is at least 2 and
there are exactly two numbers occurring
odd number of times. */
static void printTwoOdd( int arr[], int size)
{
/* Will hold XOR of two odd occurring elements */
int xor2 = arr[ 0 ];

/* Will have only single set bit of xor2 */
int set_bit_no;
int i;
int n = size - 2 ;
int x = 0 , y = 0 ;

/* Get the xor of all elements in arr[].
The xor will basically be xor of two
odd occurring elements */
for (i = 1 ; i < size; i++)
xor2 = xor2 ^ arr[i];

/* Get one set bit in the xor2. We get
rightmost set bit in the following
line as it is easy to get */
set_bit_no = xor2 & ~(xor2- 1 );

/* Now divide elements in two sets:
1) The elements having the
corresponding bit as 1.
2) The elements having the
corresponding bit as 0.  */
for (i = 0 ; i < size; i++)
{
/* XOR of first set is finally going
to hold one odd occurring number x */
if ((arr[i] & set_bit_no)> 0 )
x = x ^ arr[i];

/* XOR of second set is finally going
to hold the other odd occurring number y */
else
y = y ^ arr[i];
}

System.out.println( "The two ODD elements are " +
x + " & " + y);
}

// main function
public static void main (String[] args)
{
int arr[] = { 4 , 2 , 4 , 5 , 2 , 3 , 3 , 1 };
int arr_size = arr.length;
printTwoOdd(arr, arr_size);
}
}``````

## Python3

``````# Python3 program to find the
# two odd occurring elements

# Prints two numbers that occur odd
# number of times. The function assumes
# that the array size is at least 2 and
# there are exactly two numbers occurring
# odd number of times.
def printTwoOdd(arr, size):

# Will hold XOR of two odd occurring elements
xor2 = arr[ 0 ]

# Will have only single set bit of xor2
set_bit_no = 0
n = size - 2
x, y = 0 , 0

# Get the xor of all elements in arr[].
# The xor will basically be xor of two
# odd occurring elements
for i in range ( 1 , size):
xor2 = xor2 ^ arr[i]

# Get one set bit in the xor2. We get
# rightmost set bit in the following
# line as it is easy to get
set_bit_no = xor2 & ~(xor2 - 1 )

# Now divide elements in two sets:
# 1) The elements having the corresponding bit as 1.
# 2) The elements having the corresponding bit as 0.
for i in range (size):

# XOR of first set is finally going to
# hold one odd  occurring number x
if (arr[i] & set_bit_no):
x = x ^ arr[i]

# XOR of second set is finally going
# to hold the other odd occurring number y
else :
y = y ^ arr[i]

print ( "The two ODD elements are" , x, "&" , y)

# Driver Code
arr = [ 4 , 2 , 4 , 5 , 2 , 3 , 3 , 1 ]
arr_size = len (arr)
printTwoOdd(arr, arr_size)

# This code is contributed by Anant Agarwal.``````

## C#

``````// C# program to find two odd
// occurring elements
using System;

class main
{

// Prints two numbers that occur
// odd number of times. Function
// assumes that array size is at
// least 2 and there are exactly
// two numbers occurring odd number
// of times.
static void printTwoOdd( int []arr, int size) {

// Will hold XOR of two odd
//occurring elements
int xor2 = arr[0];

// Will have only single set
// bit of xor2
int set_bit_no;
int i;

//int n = size - 2;
int x = 0, y = 0;

// Get the xor of all the elements
// in arr[].The xor will basically
// be xor of two odd occurring
// elements
for (i = 1; i < size; i++)
xor2 = xor2 ^ arr[i];

// Get one set bit in the xor2.
// We get rightmost set bit in
// the following line as it is
// to get.
set_bit_no = xor2 & ~(xor2-1);

// divide elements in two sets:
// 1) The elements having the
// corresponding bit as 1.
// 2) The elements having the
// corresponding bit as 0.
for (i = 0; i < size; i++)
{
// XOR of first set is finally
// going to hold one odd
// occurring number x
if ((arr[i] & set_bit_no)>0)
x = x ^ arr[i];

// XOR of second set is finally
// going to hold the other
// odd occurring number y
else
y = y ^ arr[i];
}

Console.WriteLine( "The two ODD elements are " +
x + " & " + y);
}

// main function
public static void Main()
{
int []arr = {4, 2, 4, 5, 2, 3, 3, 1};
int arr_size = arr.Length;
printTwoOdd(arr, arr_size);
}
}

//This code is contributed by Anant Agarwal.``````

## 的PHP

``````<?php
// PHP program to find the
// two odd occurring elements

/* Prints two numbers that occur
odd number of times. The
function assumes that the
array size is at least 2 and
there are exactly two numbers
occurring odd number of times. */
function printTwoOdd( \$arr , \$size )
{

// Will hold XOR of two
// odd occurring elements
\$xor2 = \$arr [0];

// Will have only single
// set bit of xor2
\$set_bit_no ;

\$i ;
\$n = \$size - 2;
\$x = 0; \$y = 0;

// Get the xor of all elements
// in arr[]. The xor will basically
// be xor of two odd occurring
// elements
for ( \$i = 1; \$i < \$size ; \$i ++)
\$xor2 = \$xor2 ^ \$arr [ \$i ];

// Get one set bit in the xor2.
// We get rightmost set bit
// in the following line as
// it is easy to get
\$set_bit_no = \$xor2 & ~( \$xor2 -1);

/* Now divide elements in two sets:
1) The elements having the
corresponding bit as 1.
2) The elements having the
corresponding bit as 0. */
for ( \$i = 0; \$i < \$size ; \$i ++)
{

/* XOR of first set is finally
going to hold one odd
occurring number x */
if ( \$arr [ \$i ] & \$set_bit_no )
\$x = \$x ^ \$arr [ \$i ];

/* XOR of second set is finally
going to hold the other
odd occurring number y */
else
\$y = \$y ^ \$arr [ \$i ];
}

echo "The two ODD elements are " , \$x , " & " , \$y ;
}

// Driver Code
\$arr = array (4, 2, 4, 5, 2, 3, 3, 1);
\$arr_size = sizeof( \$arr );
printTwoOdd( \$arr , \$arr_size );

// This code is Contributed by Ajit
?>``````

``The two ODD elements are 5 & 1``