多數元素 · GeeksForGeeks 中文系列教程

# 多數元素 > 原文： [https://www.geeksforgeeks.org/majority-element/](https://www.geeksforgeeks.org/majority-element/) 編寫一個接受數組并打印多數元素（如果存在）的函數，否則打印“無多數元素”。大小為 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 ``` // 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 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（使用[二分搜索樹](https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/)）** * **方法**：在 BST 中一個接一個地插入元素，如果已經存在一個元素，則增加節點的計數。在任何階段，如果節點數超過 n / 2，則返回。 * **算法**： 1. 創建一個二分搜索樹，如果在二分搜索樹中輸入相同的元素，則節點的頻率會增加。 2. 遍歷數組并將元素插入二叉搜索樹。 3. 如果任何節點的最大頻率大于數組大小的一半，則執行有序遍歷并找到頻率大于一半的節點 4. 其他打印無多數元素。 * **Implementation:** ``` // 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 Program to test above functions? 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);? ????} ????if(ma>(size/2)) ????????inorder(root,size); ????else? ????????cout<<"No majority element\n"; ????return 0;? }? ``` **輸出**： ``` 3 ``` * **復雜度分析**： * **時間復雜度**：如果使用[二分搜索樹](https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/)，則時間復雜度將為 O（n ^ 2）。如果使用[自平衡二分搜索](http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)樹，則其為 O（nlogn） * **輔助空間**：`O(n)`。由于需要額外的空間才能將數組存儲在樹中。 **方法 3（使用摩爾投票算法）**： * **Approach:** This is a two-step process. * 第一步給出的元素可能是數組中的多數元素。如果數組中存在多數元素，則此步驟一定會返回多數元素，否則，它將返回多數元素的候選項。 * 檢查從上述步驟獲得的元素是否為多數元素。這一步是必要的，因為可能沒有多數元素。 **第 1 步：找到候選人** 在`O(n)`中起作用的第一階段算法稱為摩爾投票算法。該算法的基本思想是，如果可以用與 *e* 不同的所有其他元素取消元素 *e* 的每次出現，則 *e* 將會存在直到如果是多數元素，則結束。 **步驟 2：檢查步驟 1 中獲得的元素是否為多數元素。** 遍歷數組并檢查找到的元素的計數是否大于數組大小的一半，然后打印答案，否則打印“無多數元素”。 * **算法**： 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 function to test above functions */ 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 function to test above functions */ int main() { ????int a[] = {1, 3, 3, 1, 2}; ????int size = (sizeof(a))/sizeof(a[0]); ????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 program to test the above functions */ ????public static void main(String[] args)? ????{ ????????MajorityElement majorelement = new MajorityElement(); ????????int a[] = new int[]{1, 3, 3, 1, 2}; ????????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 program to test above functions A = [1, 3, 3, 1, 2] 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; ????????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(n)`。由于需要兩次遍歷數組，因此時間復雜度是線性的。 * **輔助空間**：`O(1)`。由于不需要額外的空間。 **方法 4（使用哈希圖）**： * **方法**：就時間復雜度而言，此方法在某種程度上類似于摩爾投票算法，但是在這種情況下，不需要第二步的摩爾投票算法。但是像往常一樣，這里的空間復雜度變為`O(n)`。在 Hashmap（鍵-值對）中，在值上，維護每個元素（鍵）的計數，每當該計數大于數組長度的一半時，返回該鍵（多數元素）。 * **算法**： 1. 創建一個哈希圖來存儲鍵值對，即元素頻率對。 2. 從頭到尾遍歷數組。 3. 對于數組中的每個元素，如果該元素不作為鍵存在，則將該元素插入哈希圖中，否則獲取鍵的值（array [i]）并將其值增加 1 4. 如果計數大于一半，則打印多數元素并中斷。 5. 如果找不到多數元素，則打印“無多數元素” * **Implementation:** ## 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 by? karan 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 提出的建議。** * **復雜度分析**： * **時間復雜度**：`O(n)`。需要對數組進行一次遍歷，因此時間復雜度是線性的。 * **輔助空間**：`O(n)`。由于哈希圖需要線性空間。 **方法 5** * **方法**：想法是對數組進行排序。排序使數組中的相似元素相鄰，因此遍歷數組并更新計數，直到當前元素與上一個元素相似為止。如果頻率超過數組大小的一半，則打印多數元素。 * **算法**： 1. 對數組進行排序，然后創建一個變量計數和上一個 *prev = INT_MIN* 。 2. 從頭到尾遍歷元素。 3. 如果當前元素等于前一個元素，則增加計數。 4. 否則將計數設置為 1。 5. 如果計數大于數組大小的一半，則將元素打印為多數元素并中斷。 6. 如果找不到多數元素，則打印“無多數元素” * **Implementation:** ``` // 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（nlogn）。排序需要`O(N log N)`時間復雜度。 * **輔助空間**：`O(1)`。由于不需要額外的空間。