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

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

## 本文概述

``````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``````

``````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``````

``````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``````

## 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``