首页 > 代码库 > 【leetcode】Majority Element

【leetcode】Majority Element

2024-08-09 18:21:10   218人阅读

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

方法1，采用一个map，存储每一个变量的数量，最后得出个数大于n/2的元素
 1 class Solution { 2 public: 3     int majorityElement(vector<int> &num) { 4         5         int n=num.size(); 6         int result;           7         map<int,int> num2count; 8   9         for(int i=0;i<n;i++)10         {11             if(num2count.find(num[i])!=num2count.end())12             {13                 num2count[num[i]]++;14             }15             else16             {17                 num2count[num[i]]=1;18             }19         }20        21         map<int,int>::iterator it=num2count.begin();22         while(it!=num2count.end())23         {24             if(it->second>n/2)25             {26                 result=it->first;27                 break;                 28             }              29             it++;30         }31         return result;32     }33 };

 

 
 
方法2，先排序，然后统计
 
 1 class Solution { 2 public: 3     int majorityElement(vector<int> &num) { 4         5         sort(num.begin(),num.end()); 6         int result=num[0]; 7         int count=0; 8         int max_count=1; 9         int cur=num[0];10        11         for(int i=0;i<num.size();i++)12         {13             if(num[i]==cur) 14             {15                 count++;16             }17             else18             {19  20                 if(count>max_count)21                 {22                     result=cur;23                     max_count=count;24                 }25                 cur=num[i];26                 count=1;27             }28         }29        30         if(count>max_count)31         {32             result=cur;33         }34        35         return result;36  37     }38 };

 

 
方法3，采用随机选取元素的方法，进行统计：
 1 #define random(x) (rand()%x) 2 class Solution { 3 public: 4     int majorityElement(vector<int> &num) { 5         6         int result; 7         while(1) 8         { 9             result=num[random(num.size())];10             int count=0;11             for(int i=0;i<num.size();i++)12             {13                 if(num[i]==result)14                 {15                     count++;16                 }17             }18             if(count>num.size()/2)19             {20                 break;21             }22         }23         return result;24     }25 };

 

 
多数投票算法：
过程：
Runtime: O( n ) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x: 
  1. If the counter is 0, we set the current candidate to x and the counter to 1.
  2. If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.
After one pass, the current candidate is the majority element. Runtime complexity = O( n ).
 
 
 1 class Solution { 2 public: 3     int majorityElement(vector<int> &num) {       4         5         int count=0; 6         int i=0; 7         int result; 8         while(i<num.size()) 9         {10             if(count==0)11             {12                 result=num[i];13                 count++;14             }15             else16             {17                 if(result==num[i])18                 {19                     count++;20                 }21                 else22                 {23                     count--;24                 }25             }26             i++;27         }       28         return result;       29     }30 };

 

【leetcode】Majority Element


联系
我们