本文概述
编写一个接受数组并打印多数元素(如果存在)的函数, 否则打印"无多数元素"。一种多数元素大小为n的数组A []中的元素是出现超过n / 2次的元素(因此, 最多有一个这样的元素)。
例子 ：
Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4
Explanation: The frequency of 4 is 5 which is greater
than the half of the size of the array size.
Input : {3, 3, 4, 2, 4, 4, 2, 4}
Output : No Majority Element
Explanation: There is no element whose frequency is
greater than the half of the size of the array size.推荐：请在"
实践
首先, 在继续解决方案之前。
方法1
- 方法：基本解决方案是有两个循环并跟踪所有不同元素的最大计数。如果最大计数大于n / 2, 则中断循环并返回具有最大计数的元素。如果最大数量不超过n / 2, 则多数元素不存在。
- 算法：
- 创建一个变量来存储最大数量, 计数= 0
- 从头到尾遍历整个数组。
- 对于数组中的每个元素, 运行另一个循环以查找给定数组中相似元素的数量。
- 如果计数大于最大计数, 则更新最大计数并将索引存储在另一个变量中。
- 如果最大计数大于数组大小的一半, 则打印该元素。否则, 没有多数元素。
以下是上述想法的实现：
C ++
// C++ program to find Majority
// element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find Majority element
// in an array
void findMajority( int arr[], int n)
{
int maxCount = 0;
int index = -1; // sentinels
for ( int i = 0; i < n; i++) {
int count = 0;
for ( int j = 0; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
// update maxCount if count of
// current element is greater
if (count > maxCount) {
maxCount = count;
index = i;
}
}
// if maxCount is greater than n/2
// return the corresponding element
if (maxCount > n / 2)
cout << arr[index] << endl;
else
cout << "No Majority Element" << endl;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
// Function calling
findMajority(arr, n);
return 0;
}Java
// Java program to find Majority
// element in an array
import java.io.*;
class GFG {
// Function to find Majority element
// in an array
static void findMajority( int arr[], int n)
{
int maxCount = 0 ;
int index = - 1 ; // sentinels
for ( int i = 0 ; i < n; i++) {
int count = 0 ;
for ( int j = 0 ; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
// update maxCount if count of
// current element is greater
if (count > maxCount) {
maxCount = count;
index = i;
}
}
// if maxCount is greater than n/2
// return the corresponding element
if (maxCount > n / 2 )
System.out.println(arr[index]);
else
System.out.println( "No Majority Element" );
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1 , 1 , 2 , 1 , 3 , 5 , 1 };
int n = arr.length;
// Function calling
findMajority(arr, n);
}
// This code is contributed by ajit.
}Python 3
# Python 3 program to find Majority
# element in an array
# Function to find Majority
# element in an array
def findMajority(arr, n):
maxCount = 0
index = - 1 # sentinels
for i in range (n):
count = 0
for j in range (n):
if (arr[i] = = arr[j]):
count + = 1
# update maxCount if count of
# current element is greater
if (count > maxCount):
maxCount = count
index = i
# if maxCount is greater than n/2
# return the corresponding element
if (maxCount > n / / 2 ):
print (arr[index])
else :
print ( "No Majority Element" )
# Driver code
if __name__ = = "__main__" :
arr = [ 1 , 1 , 2 , 1 , 3 , 5 , 1 ]
n = len (arr)
# Function calling
findMajority(arr, n)
# This code is contributed
# by ChitraNayalC#
// C# program to find Majority
// element in an array
using System;
public class GFG {
// Function to find Majority element
// in an array
static void findMajority( int [] arr, int n)
{
int maxCount = 0;
int index = -1; // sentinels
for ( int i = 0; i < n; i++) {
int count = 0;
for ( int j = 0; j < n; j++) {
if (arr[i] == arr[j])
count++;
}
// update maxCount if count of
// current element is greater
if (count > maxCount) {
maxCount = count;
index = i;
}
}
// if maxCount is greater than n/2
// return the corresponding element
if (maxCount > n / 2)
Console.WriteLine(arr[index]);
else
Console.WriteLine( "No Majority Element" );
}
// Driver code
static public void Main()
{
int [] arr = { 1, 1, 2, 1, 3, 5, 1 };
int n = arr.Length;
// Function calling
findMajority(arr, n);
}
// This code is contributed by Tushil..
}的PHP
<?php
// PHP program to find Majority
// element in an array
// Function to find Majority element
// in an array
function findMajority( $arr , $n )
{
$maxCount = 0;
$index = -1; // sentinels
for ( $i = 0; $i < $n ; $i ++)
{
$count = 0;
for ( $j = 0; $j < $n ; $j ++)
{
if ( $arr [ $i ] == $arr [ $j ])
$count ++;
}
// update maxCount if count of
// current element is greater
if ( $count > $maxCount )
{
$maxCount = $count ;
$index = $i ;
}
}
// if maxCount is greater than n/2
// return the corresponding element
if ( $maxCount > $n /2)
echo $arr [ $index ] . "\n" ;
else
echo "No Majority Element" . "\n" ;
}
// Driver code
$arr = array (1, 1, 2, 1, 3, 5, 1);
$n = sizeof( $arr );
// Function calling
findMajority( $arr , $n );
// This code is contributed
// by Akanksha Rai输出如下
1复杂性分析：
- 时间复杂度：O(n * n)。
需要两个循环都从头到尾遍历数组的嵌套循环, 因此时间复杂度为O(n ^ 2)。 - 辅助空间：O(1)。
由于任何操作都不需要额外的空间, 因此空间复杂度是恒定的。
方法2(使用
二进制搜索树
)
- 方法：在BST中一一插入元素, 如果已经存在一个元素, 则增加节点的计数。在任何阶段, 如果节点数大于n / 2, 则返回。
- 算法：
- 创建一个二进制搜索树, 如果在二进制搜索树中输入相同的元素, 则节点的频率会增加。
- 遍历数组并将元素插入二叉搜索树。
- 如果任何节点的最大频率大于数组大小的一半, 则执行有序遍历并找到频率大于一半的节点
- 其他打印无多数元素。
下面是上述想法的实现：
CPP14
// C++ program to demonstrate insert operation in binary
// search tree.
#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
int c = 0;
struct node *left, *right;
};
// A utility function to create a new BST node
struct node* newNode( int item)
{
struct node* temp
= ( struct node*) malloc ( sizeof ( struct node));
temp->key = item;
temp->c = 1;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to insert a new node with given key in
// BST
struct node* insert( struct node* node, int key, int & ma)
{
// If the tree is empty, return a new node
if (node == NULL) {
if (ma == 0)
ma = 1;
return newNode(key);
}
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left, key, ma);
else if (key > node->key)
node->right = insert(node->right, key, ma);
else
node->c++;
// find the max count
ma = max(ma, node->c);
// return the (unchanged) node pointer
return node;
}
// A utility function to do inorder traversal of BST
void inorder( struct node* root, int s)
{
if (root != NULL) {
inorder(root->left, s);
if (root->c > (s / 2))
printf ( "%d \n" , root->key);
inorder(root->right, s);
}
}
// Driver Code
int main()
{
int a[] = { 1, 3, 3, 3, 2 };
int size = ( sizeof (a)) / sizeof (a[0]);
struct node* root = NULL;
int ma = 0;
for ( int i = 0; i < size; i++) {
root = insert(root, a[i], ma);
}
// Function call
if (ma > (size / 2))
inorder(root, size);
else
cout << "No majority element\n" ;
return 0;
}Python3
# C++ program to demonstrate insert operation in binary
# search tree.
# class for creating node
class Node():
def __init__( self , data):
self .data = data
self .left = None
self .right = None
self .count = 1 # count of number of times data is inserted in tree
# class for binary search tree
# it initialises tree with None root
# insert function inserts node as per BST rule
# and also checks for majority element
# if no majority element is found yet, it returns None
class BST():
def __init__( self ):
self .root = None
def insert( self , data, n):
out = None
if ( self .root = = None ):
self .root = Node(data)
else :
out = self .insertNode( self .root, data, n)
return out
def insertNode( self , currentNode, data, n):
if (currentNode.data = = data):
currentNode.count + = 1
if (currentNode.count > n / / 2 ):
return currentNode.data
else :
return None
elif (currentNode.data < data):
if (currentNode.right):
self .insertNode(currentNode.right, data, n)
else :
currentNode.right = Node(data)
elif (currentNode.data > data):
if (currentNode.left):
self .insertNode(currentNode.left, data, n)
else :
currentNode.left = Node(data)
# Driver code
# declaring an array
arr = [ 3 , 2 , 3 ]
n = len (arr)
# declaring None tree
tree = BST()
flag = 0
for i in range (n):
out = tree.insert(arr[i], n)
if (out ! = None ):
print (arr[i])
flag = 1
break
if (flag = = 0 ):
print ( "No Majority Element" )输出如下
3复杂度分析：
- 时间复杂度：如果一个二进制搜索树则时间复杂度将为O(n ^ 2)。如果一个自平衡二进制搜索使用树, 它将是O(nlogn)
- 辅助空间：上)。
由于需要额外的空间才能将数组存储在树中。
方法3(使用摩尔的投票算法)：
- 方法：这是一个两步过程。
- 第一步给出的元素可能是数组中的多数元素。如果数组中存在多数元素, 则此步骤肯定会返回多数元素, 否则, 它将返回多数元素的候选项。
- 检查从上述步骤获得的元素是否为多数元素。这一步是必要的, 因为可能没有多数元素。
- 算法：
- 遍历每个元素, 并维护一个多数元素计数和一个多数索引, maj_index
- 如果下一个元素相同, 则增加计数；如果下一个元素不同, 则减少计数。
- 如果计数达到0, 则将maj_index更改为当前元素, 然后将计数再次设置为1。
- 现在再次遍历数组, 找到找到的多数元素计数。
- 如果计数大于数组大小的一半, 则打印元素
- 没有多数元素的其他印刷品
下面是上述想法的实现：
C ++
// C++ Program for finding out
// majority element in an array
#include <bits/stdc++.h>
using namespace std;
/* Function to find the candidate for Majority */
int findCandidate( int a[], int size)
{
int maj_index = 0, count = 1;
for ( int i = 1; i < size; i++) {
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0) {
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
/* Function to check if the candidate
occurs more than n/2 times */
bool isMajority( int a[], int size, int cand)
{
int count = 0;
for ( int i = 0; i < size; i++)
if (a[i] == cand)
count++;
if (count > size / 2)
return 1;
else
return 0;
}
/* Function to print Majority Element */
void printMajority( int a[], int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/
if (isMajority(a, size, cand))
cout << " " << cand << " " ;
else
cout << "No Majority Element" ;
}
/* Driver code */
int main()
{
int a[] = { 1, 3, 3, 1, 2 };
int size = ( sizeof (a)) / sizeof (a[0]);
// Function calling
printMajority(a, size);
return 0;
}C
/* Program for finding out majority element in an array */
#include <stdio.h>
#define bool int
int findCandidate( int *, int );
bool isMajority( int *, int , int );
/* Function to print Majority Element */
void printMajority( int a[], int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/
if (isMajority(a, size, cand))
printf ( " %d " , cand);
else
printf ( "No Majority Element" );
}
/* Function to find the candidate for Majority */
int findCandidate( int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for (i = 1; i < size; i++) {
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0) {
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
/* Function to check if the candidate occurs more than n/2
* times */
bool isMajority( int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if (a[i] == cand)
count++;
if (count > size / 2)
return 1;
else
return 0;
}
/* Driver code */
int main()
{
int a[] = { 1, 3, 3, 1, 2 };
int size = ( sizeof (a)) / sizeof (a[0]);
// Function call
printMajority(a, size);
getchar ();
return 0;
}Java
/* Program for finding out majority element in an array */
class MajorityElement {
/* Function to print Majority Element */
void printMajority( int a[], int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/
if (isMajority(a, size, cand))
System.out.println( " " + cand + " " );
else
System.out.println( "No Majority Element" );
}
/* Function to find the candidate for Majority */
int findCandidate( int a[], int size)
{
int maj_index = 0 , count = 1 ;
int i;
for (i = 1 ; i < size; i++) {
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0 ) {
maj_index = i;
count = 1 ;
}
}
return a[maj_index];
}
/* Function to check if the candidate occurs more
than n/2 times */
boolean isMajority( int a[], int size, int cand)
{
int i, count = 0 ;
for (i = 0 ; i < size; i++) {
if (a[i] == cand)
count++;
}
if (count > size / 2 )
return true ;
else
return false ;
}
/* Driver code */
public static void main(String[] args)
{
MajorityElement majorelement
= new MajorityElement();
int a[] = new int [] { 1 , 3 , 3 , 1 , 2 };
// Function call
int size = a.length;
majorelement.printMajority(a, size);
}
}
// This code has been contributed by Mayank Jaiswalpython
# Program for finding out majority element in an array
# Function to find the candidate for Majority
def findCandidate(A):
maj_index = 0
count = 1
for i in range ( len (A)):
if A[maj_index] = = A[i]:
count + = 1
else :
count - = 1
if count = = 0 :
maj_index = i
count = 1
return A[maj_index]
# Function to check if the candidate occurs more than n/2 times
def isMajority(A, cand):
count = 0
for i in range ( len (A)):
if A[i] = = cand:
count + = 1
if count > len (A) / 2 :
return True
else :
return False
# Function to print Majority Element
def printMajority(A):
# Find the candidate for Majority
cand = findCandidate(A)
# Print the candidate if it is Majority
if isMajority(A, cand) = = True :
print (cand)
else :
print ( "No Majority Element" )
# Driver code
A = [ 1 , 3 , 3 , 1 , 2 ]
# Function call
printMajority(A)C#
// C# Program for finding out majority element in an array
using System;
class GFG {
/* Function to print Majority Element */
static void printMajority( int [] a, int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/
if (isMajority(a, size, cand))
Console.Write( " " + cand + " " );
else
Console.Write( "No Majority Element" );
}
/* Function to find the candidate for Majority */
static int findCandidate( int [] a, int size)
{
int maj_index = 0, count = 1;
int i;
for (i = 1; i < size; i++) {
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0) {
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
// Function to check if the candidate
// occurs more than n/2 times
static bool isMajority( int [] a, int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++) {
if (a[i] == cand)
count++;
}
if (count > size / 2)
return true ;
else
return false ;
}
// Driver Code
public static void Main()
{
int [] a = { 1, 3, 3, 1, 2 };
int size = a.Length;
// Function call
printMajority(a, size);
}
}
// This code is contributed by Sam007的PHP
<?php
// PHP Program for finding out majority
// element in an array
// Function to find the candidate
// for Majority
function findCandidate( $a , $size )
{
$maj_index = 0;
$count = 1;
for ( $i = 1; $i < $size ; $i ++)
{
if ( $a [ $maj_index ] == $a [ $i ])
$count ++;
else
$count --;
if ( $count == 0)
{
$maj_index = $i ;
$count = 1;
}
}
return $a [ $maj_index ];
}
// Function to check if the candidate
// occurs more than n/2 times
function isMajority( $a , $size , $cand )
{
$count = 0;
for ( $i = 0; $i < $size ; $i ++)
if ( $a [ $i ] == $cand )
$count ++;
if ( $count > $size / 2)
return 1;
else
return 0;
}
// Function to print Majority Element
function printMajority( $a , $size )
{
/* Find the candidate for Majority*/
$cand = findCandidate( $a , $size );
/* Print the candidate if it is Majority*/
if (isMajority( $a , $size , $cand ))
echo " " , $cand , " " ;
else
echo "No Majority Element" ;
}
// Driver Code
$a = array (1, 3, 3, 1, 2);
$size = sizeof( $a );
// Function calling
printMajority( $a , $size );
// This code is contributed by jit_t
?>输出如下
No Majority Element复杂度分析：
- 时间复杂度：上)。
由于需要两次遍历数组, 因此时间复杂度是线性的。 - 辅助空间：O(1)。
由于不需要额外的空间。
方法4(使用哈希图)：
- 方法：就时间复杂度而言, 此方法在某种程度上类似于Moore投票算法, 但是在这种情况下, 不需要Moore投票算法的第二步。但是像往常一样, 这里的空间复杂度变为O(n)。
在Hashmap(键-值对)中, 在值为value时, 维护每个元素(键)的计数, 并且只要该计数大于数组长度的一半, 则返回该键(多数元素)。
- 算法：
- 创建一个哈希图以存储键值对, 即元素频率对。
- 从头到尾遍历数组。
- 对于数组中的每个元素, 如果该元素不作为键存在, 则将该元素插入哈希图中, 否则获取键的值(array [i])并将其值增加1
- 如果计数大于一半, 则打印多数元素并中断。
- 如果找不到多数元素, 则打印"无多数元素"
下面是上述想法的实现：
C ++
/* C++ program for finding out majority
element in an array */
#include <bits/stdc++.h>
using namespace std;
void findMajority( int arr[], int size)
{
unordered_map< int , int > m;
for ( int i = 0; i < size; i++)
m[arr[i]]++;
int count = 0;
for ( auto i : m)
{
if (i.second > size / 2)
{
count =1;
cout << "Majority found :- " << i.first<<endl;
break ;
}
}
if (count == 0)
cout << "No Majority element" << endl;
}
// Driver code
int main()
{
int arr[] = {2, 2, 2, 2, 5, 5, 2, 3, 3};
int n = sizeof (arr) / sizeof (arr[0]);
// Function calling
findMajority(arr, n);
return 0;
}
// This code is contributed by codeMan_dJava
import java.util.HashMap;
/* Program for finding out majority element in an array */
class MajorityElement
{
private static void findMajority( int [] arr)
{
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for ( int i = 0 ; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
int count = map.get(arr[i]) + 1 ;
if (count > arr.length / 2 ) {
System.out.println( "Majority found :- " + arr[i]);
return ;
} else
map.put(arr[i], count);
}
else
map.put(arr[i], 1 );
}
System.out.println( " No Majority element" );
}
/* Driver program to test the above functions */
public static void main(String[] args)
{
int a[] = new int []{ 2 , 2 , 2 , 2 , 5 , 5 , 2 , 3 , 3 };
findMajority(a);
}
}
// This code is contributed by karan malhotraPython3
# Python program for finding out majority
# element in an array
def findMajority(arr, size):
m = {}
for i in range (size):
if arr[i] in m:
m[arr[i]] + = 1
else :
m[arr[i]] = 1
count = 0
for key in m:
if m[key] > size / 2 :
count = 1
print ( "Majority found :-" , key)
break
if (count = = 0 ):
print ( "No Majority element" )
# Driver code
arr = [ 2 , 2 , 2 , 2 , 5 , 5 , 2 , 3 , 3 ]
n = len (arr)
# Function calling
findMajority(arr, n)
# This code is contributed by ankush_953C#
// C# Program for finding out majority
// element in an array
using System;
using System.Collections.Generic;
class GFG
{
private static void findMajority( int [] arr)
{
Dictionary< int , int > map = new Dictionary< int , int >();
for ( int i = 0; i < arr.Length; i++)
{
if (map.ContainsKey(arr[i]))
{
int count = map[arr[i]] + 1;
if (count > arr.Length / 2)
{
Console.WriteLine( "Majority found :- " +
arr[i]);
return ;
}
else
{
map[arr[i]] = count;
}
}
else
{
map[arr[i]] = 1;
}
}
Console.WriteLine( " No Majority element" );
}
// Driver Code
public static void Main( string [] args)
{
int [] a = new int []{2, 2, 2, 2, 5, 5, 2, 3, 3};
findMajority(a);
}
}
// This code is contributed by Shrikant13输出如下
Majority found :- 2复杂度分析：
- 时间复杂度：上)。
需要对数组进行一次遍历, 因此时间复杂度是线性的。 - 辅助空间：上)。
由于哈希图需要线性空间。
感谢Ashwani Tanwar, Karan Malhotra提出的建议。
方法5
- 方法：这个想法是对数组进行排序。排序使数组中的相似元素相邻, 因此遍历数组并更新计数, 直到当前元素与上一个元素相似为止。如果频率超过数组大小的一半, 则打印多数元素。
- 算法：
- 对数组进行排序, 并创建一个变量数和上一个, 上一个= INT_MIN.
- 从头到尾遍历元素。
- 如果当前元素等于前一个元素, 则增加计数。
- 否则将计数设置为1。
- 如果计数大于数组大小的一半, 则将元素打印为多数元素并中断。
- 如果未找到多数元素, 则打印"无多数元素"
以下是上述想法的实现：
CPP
// C++ program to find Majority
// element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find Majority element
// in an array
// it returns -1 if there is no majority element
int majorityElement( int *arr, int n)
{
// sort the array in O(nlogn)
sort(arr, arr+n);
int count = 1, max_ele = -1, temp = arr[0], ele, f=0;
for ( int i=1;i<n;i++)
{
// increases the count if the same element occurs
// otherwise starts counting new element
if (temp==arr[i])
{
count++;
}
else
{
count = 1;
temp = arr[i];
}
// sets maximum count
// and stores maximum occured element so far
// if maximum count becomes greater than n/2
// it breaks out setting the flag
if (max_ele<count)
{
max_ele = count;
ele = arr[i];
if (max_ele>(n/2))
{
f = 1;
break ;
}
}
}
// returns maximum occured element
// if there is no such element, returns -1
return (f==1 ? ele : -1);
}
// Driver code
int main()
{
int arr[] = {1, 1, 2, 1, 3, 5, 1};
int n = sizeof (arr) / sizeof (arr[0]);
// Function calling
cout<<majorityElement(arr, n);
return 0;
}输出如下
1复杂度分析：
- 时间复杂度：O(登录)。
排序需要O(n log n)时间复杂度。 - 辅助空间：O(1)。
由于不需要额外的空间。
![从字法上最小长度N的排列，使得对于正好为K个索引，a[i] a[i]+1](https://www.lsbin.com/wp-content/themes/begin%20lts/img/loading.png)
