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

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

本文概述

给定一个未排序的数组, 其中包含除两个数字以外的所有数字的偶数个出现次数。找出两个在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)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: