算法题：查找多数元素|S3（位魔术）

2021年4月26日16:35:01 发表评论 699 次浏览

本文概述

先决条件： 多数元素, 多数元素|S2(哈希)

给定大小为N的数组, 找到多数元素。多数元素是在给定数组中出现n/2次以上的元素。

例子：

Input: {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output: 4

Input: {3, 3, 6, 2, 4, 4, 2, 4}
Output: No Majority Element

方法：

在这篇文章中, 我们借助于数组中存在的数字的二进制表示来解决该问题。

任务是找到出现次数超过n/2次的元素。因此, 它看起来比所有其他数字的总和还多。

因此, 我们从数组每个数字的LSB(最低有效位)开始, 计算设置的数组数字。如果有任何设置大于n/2个数字, 然后在我们的多数元素中设置该位。

上面的方法之所以有效, 是因为对于其他所有数字, 设置的位数不会超过n/2, 因为多数元素的出现次数超过n/2次。

让我们借助示例

Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Binary representation of the same are:

3 - 0 1 1
3 - 0 1 1
4 - 1 0 0
2 - 0 1 0
4 - 1 0 0
4 - 1 0 0
2 - 0 1 0
4 - 1 0 0
4 - 1 0 0
----------
  - 5 4 0

在这里n为9, 因此n/2 = 4, 并且右数第3个位满足count> 4, 因此在多数元素中设置, 其他所有位均未设置。

因此, 我们的多数元素是1 0 0, 这是4

但是还有更多, 当数组中存在多数元素时, 这种方法就可以工作。如果不存在怎么办？

让我们借助此示例进行查看：

Input : {3, 3, 6, 2, 4, 4, 2, 4}
Binary representation of the same are:

3 - 0 1 1
3 - 0 1 1
6 - 1 1 0
2 - 0 1 0
4 - 1 0 0
4 - 1 0 0
2 - 0 1 0
4 - 1 0 0
----------
  - 4 5 0

在这里n为8, 因此n/2 = 4, 并且右数第二位满足count> 4, 因此应在多数元素中将其设置为1, 其他所有位均未设置。

因此, 据此, 我们的多数元素为0 1 0, 即2但是实际上多数元素都不存在于数组中。因此, 我们还要对数组进行一次遍历, 以确保此元素出现的次数超过n/2次。

这是以上想法的实现

C ++

#include <iostream>
using namespace std;
  
void findMajority( int arr[], int n)
{
     //Number of bits in the integer
     int len = sizeof ( int ) * 8;
  
     //Variable to calculate majority element
     int number = 0;
  
     //Loop to iterate through all the bits of number
     for ( int i = 0; i <len; i++) {
         int count = 0;
         //Loop to iterate through all elements in array
         //to count the total set bit
         //at position i from right
         for ( int j = 0; j <n; j++) {
             if (arr[j] & (1 <<i))
                 count++;
         }
         //If the total set bits exceeds n/2, //this bit should be present in majority Element.
         if (count> (n /2))
             number += (1 <<i);
     }
  
     int count = 0;
  
     //iterate through array get
     //the count of candidate majority element
     for ( int i = 0; i <n; i++)
         if (arr[i] == number)
             count++;
  
     //Verify if the count exceeds n/2
     if (count> (n /2))
         cout <<number;
     else
         cout <<"Majority Element Not Present" ;
}
  
//Driver Program
int main()
{
  
     int arr[] = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
     int n = sizeof (arr) /sizeof (arr[0]);
     findMajority(arr, n);
     return 0;
}

Java

class GFG 
{
     static void findMajority( int arr[], int n) 
     { 
         //Number of bits in the integer 
         int len = 32 ; 
      
         //Variable to calculate majority element 
         int number = 0 ; 
      
         //Loop to iterate through all the bits of number 
         for ( int i = 0 ; i <len; i++) 
         { 
             int count = 0 ; 
             //Loop to iterate through all elements in array 
             //to count the total set bit 
             //at position i from right 
             for ( int j = 0 ; j <n; j++) 
             { 
                 if ((arr[j] & ( 1 <<i)) != 0 ) 
                     count++; 
             } 
              
             //If the total set bits exceeds n/2, //this bit should be present in majority Element. 
             if (count> (n /2 )) 
                 number += ( 1 <<i); 
         } 
      
         int count = 0 ; 
      
         //iterate through array get 
         //the count of candidate majority element 
         for ( int i = 0 ; i <n; i++) 
             if (arr[i] == number) 
                 count++; 
      
         //Verify if the count exceeds n/2 
         if (count> (n /2 )) 
             System.out.println(number); 
         else
             System.out.println( "Majority Element Not Present" ); 
     } 
      
     //Driver Code
     public static void main (String[] args) 
     { 
         int arr[] = { 3 , 3 , 4 , 2 , 4 , 4 , 2 , 4 , 4 }; 
         int n = arr.length; 
         findMajority(arr, n); 
     } 
}
  
//This code is contributed by AnkitRai01

Python3

def findMajority(arr, n):
      
     # Number of bits in the integer
     Len = 32
  
     # Variable to calculate majority element
     number = 0
  
     # Loop to iterate through 
     # all the bits of number
     for i in range ( Len ):
         count = 0
          
         # Loop to iterate through all elements 
         # in array to count the total set bit
         # at position i from right
         for j in range (n):
             if (arr[j] & ( 1 <<i)):
                 count + = 1
                  
         # If the total set bits exceeds n/2, # this bit should be present in 
         # majority Element.
         if (count> (n //2 )):
             number + = ( 1 <<i)
  
     count = 0
  
     # iterate through array get
     # the count of candidate majority element
     for i in range (n):
         if (arr[i] = = number):
             count + = 1
  
     # Verify if the count exceeds n/2
     if (count> (n //2 )):
         print (number)
     else :
         print ( "Majority Element Not Present" )
  
# Driver Code
arr = [ 3 , 3 , 4 , 2 , 4 , 4 , 2 , 4 , 4 ]
n = len (arr)
findMajority(arr, n)
  
# This code is contributed by Mohit Kumar

C#

using System;
  
class GFG
{
     static void findMajority( int []arr, int n) 
     { 
         //Number of bits in the integer 
         int len = 32; 
      
         //Variable to calculate majority element 
         int number = 0; 
      
         //Loop to iterate through all the bits of number 
         for ( int i = 0; i <len; i++) 
         { 
             int countt = 0; 
              
             //Loop to iterate through all elements 
             //in array to count the total set bit 
             //at position i from right 
             for ( int j = 0; j <n; j++) 
             { 
                 if ((arr[j] & (1 <<i)) != 0) 
                     countt++; 
             } 
              
             //If the total set bits exceeds n/2, //this bit should be present in majority Element. 
             if (countt> (n /2)) 
                 number += (1 <<i); 
         } 
      
         int count = 0; 
      
         //iterate through array get 
         //the count of candidate majority element 
         for ( int i = 0; i <n; i++) 
             if (arr[i] == number) 
                 count++; 
      
         //Verify if the count exceeds n/2 
         if (count> (n /2)) 
             Console.Write(number); 
         else
             Console.Write( "Majority Element Not Present" ); 
     } 
      
     //Driver Code
     static public void Main ()
     {
         int []arr = { 3, 3, 4, 2, 4, 4, 2, 4, 4 }; 
         int n = arr.Length; 
         findMajority(arr, n); 
     } 
}
  
//This code is contributed by @Tushi..

输出如下：

4

时间复杂度：O(N)

空间复杂度：O(1)

木子山

发表评论

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