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

本文概述

C ++
Java
Python3
C#

先决条件：多数元素, 多数元素|S2(哈希)
给定大小为N的数组, 找到多数元素。多数元素是在给定数组中出现n/2次以上的元素。
例子：

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

方法：
在这篇文章中, 我们借助于数组中存在的数字的二进制表示来解决该问题。
任务是找到出现次数超过n/2次的元素。因此, 它看起来比所有其他数字的总和还多。
【算法题（查找多数元素|S3（位魔术））】因此, 我们从数组每个数字的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

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

输出如下：