本文概述【算法设计（多数元素问题）】编写一个接受数组并打印多数元素(如果存在)的函数, 否则打印"无多数元素"。一种多数元素大小为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, 则多数元素不存在。
• 算法： 
  1. 创建一个变量来存储最大数量, 计数= 0
  2. 从头到尾遍历整个数组。
  3. 对于数组中的每个元素, 运行另一个循环以查找给定数组中相似元素的数量。
  4. 如果计数大于最大计数, 则更新最大计数并将索引存储在另一个变量中。
  5. 如果最大计数大于数组大小的一半, 则打印该元素。否则, 没有多数元素。

以下是上述想法的实现：
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

// Javaprogram 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 ChitraNayal

C#

// 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, 则返回。
• 算法： 
  1. 创建一个二进制搜索树, 如果在二进制搜索树中输入相同的元素, 则节点的频率会增加。
  2. 遍历数组并将元素插入二叉搜索树。
  3. 如果任何节点的最大频率大于数组大小的一半, 则执行有序遍历并找到频率大于一半的节点
  4. 其他打印无多数元素。

下面是上述想法的实现：
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 = https://www.lsbin.com/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(使用摩尔的投票算法)：

• 方法：这是一个两步过程。
  • 第一步给出的元素可能是数组中的多数元素。如果数组中存在多数元素, 则此步骤肯定会返回多数元素, 否则, 它将返回多数元素的候选项。
  • 检查从上述步骤获得的元素是否为多数元素。这一步是必要的, 因为可能没有多数元素。
     
• 算法： 
  1. 遍历每个元素, 并维护一个多数元素计数和一个多数索引, maj_index
  2. 如果下一个元素相同, 则增加计数；如果下一个元素不同, 则减少计数。
  3. 如果计数达到0, 则将maj_index更改为当前元素, 然后将计数再次设置为1。
  4. 现在再次遍历数组, 找到找到的多数元素计数。
  5. 如果计数大于数组大小的一半, 则打印元素
  6. 没有多数元素的其他印刷品

下面是上述想法的实现：
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 Jaiswal

python

# 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时, 维护每个元素(键)的计数, 并且只要该计数大于数组长度的一半, 则返回该键(多数元素)。
   
• 算法：
  1. 创建一个哈希图以存储键值对, 即元素频率对。
  2. 从头到尾遍历数组。
  3. 对于数组中的每个元素, 如果该元素不作为键存在, 则将该元素插入哈希图中, 否则获取键的值(array [i])并将其值增加1
  4. 如果计数大于一半, 则打印多数元素并中断。
  5. 如果找不到多数元素, 则打印"无多数元素"

下面是上述想法的实现：
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_d

Java

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 bykaran malhotra

Python3

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

C#

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

• 方法：这个想法是对数组进行排序。排序使数组中的相似元素相邻, 因此遍历数组并更新计数, 直到当前元素与上一个元素相似为止。如果频率超过数组大小的一半, 则打印多数元素。
• 算法：
  1. 对数组进行排序, 并创建一个变量数和上一个, 上一个= INT_MIN.
  2. 从头到尾遍历元素。
  3. 如果当前元素等于前一个元素, 则增加计数。
  4. 否则将计数设置为1。
  5. 如果计数大于数组大小的一半, 则将元素打印为多数元素并中断。
  6. 如果未找到多数元素, 则打印"无多数元素"

以下是上述想法的实现：
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)。
  由于不需要额外的空间。

推荐阅读

• 

  凉血祛风糖浆的说明书
• 

  非师范学生当老师 非师范生怎么当上老师
• 

  linux抓网络数据命令 linux网络抓包分析工具
• 

  什么是视频滤镜，视频滤镜原理
• 

  微信声音锁登录无法识别如何解决 微信声音锁登录无法识别如何解决呢
• 

  黄芪水一个星期喝几次是合理的
• 

  圣诞语录短句简短 圣诞语录短句简短给朋友
• 

  十条笑话:儿子喜欢上隔壁家女儿，我该怎么办?
• 

  关于电脑怎么同步微信视频号的信息
• 

  易拉罐吹跑车声音教程 这么强大的操作
• 

  枯萎的玫瑰花瓣可以做什么
• 

  redis和数据库不一致时怎么解决 Redis和sql区别
• 

  天之蓝海之蓝梦之蓝 洋河海之蓝酒价格表
• 

  心烦的时候怎么办
• 

  如何在云服务器上安装PHP？ 云服务器怎么安装php
• 

  安装辅材包括哪些 安装辅材包括哪些东西
• 

  华为编程语言仓颉官网报名，谁创造了汉语
• 

  新产品上市的推广话术 新品上市广告语怎么写
• 

  廖常初plc编程及应用，PLC编程及应用 第3版 廖常初 课后答案
• 

  紫砂壶怎么选

• 算法设计（模乘逆元问题）
• Python MongoDB – create_index查询用法详细示例
• 8085程序查找8位数字的平方
• PHP SplObjectStorage contains()函数用法详细介绍
• PHP date_default_timezone_get()函数用法介绍
• JavaScript基本语法指南（注释用法实例）
• U盘做系统,本文教您U盘做系统办法
• 笔记本u盘打开,本文教您联想笔记本u盘打开的办法
• u盘乱码,本文教您u盘出现乱码的处理办法