本文概述
给定一个未排序的数组, 其中包含除两个数字以外的所有数字的偶数个出现次数。找出两个在O(n)时间复杂度和O(1)额外空间中出现奇数的数字。
例子:
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 ^ 2)。
我们可以使用排序以获取O(nLogn)时间中出现的奇数。首先使用O(nLogn)排序算法(例如合并排序, 堆排序等)对数字进行排序。对数组进行排序后, 我们要做的就是对数组进行线性扫描并打印出现的奇数。
我们也可以使用哈希。创建一个空的哈希表, 其中将包含元素及其计数。一一挑选输入数组的所有元素。在哈希表中查找选择的元素。如果在哈希表中找到该元素, 则在表中增加其计数。如果找不到该元素, 则将其输入到哈希表中, 计数为1。将所有元素输入哈希表后, 扫描哈希表并打印具有奇数的元素。这种方法平均可能需要O(n)时间, 但需要O(n)额外空间。
O(n)时间和O(1)额外空间解决方案:
这个想法类似于
这个
发布。令两个出现的奇数为x和y。我们
使用按位异或
得到x和y。
第一步是对数组中存在的所有元素进行XOR
。由于XOR运算的以下特性, 所有元素的XOR使我们对x和y进行XOR。
1)任何数字n与自身的XOR等于0, 即n ^ n = 0
2)任意数字n与0的XOR运算得到n, 即n ^ 0 = n
3)XOR是累积和关联的。
因此, 第一步之后, 我们对x和y进行了XOR。令XOR的值为xor2。 xor2中的每个置位指示x和y中的相应位具有彼此不同的值。例如, 如果x = 6(0110)并且y为15(1111), 则xor2将为(1001), xor2中的两个置位指示x和y中的相应位不同。
在第二步中, 我们选择xor2的一组位并将数组元素分成两组
。 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
时间复杂度:O(n)
辅助空间:O(1)
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。