# 169.Majority Element

## August 16, 2016

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

class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
int i=0,j=0,size=nums.size(),count=0;
int half=size/2;;
for(i=0;i<size;i++){
count=0;/*外循环每进行一次count计数变量应该重新置0*/
for(j=0;j<size;j++){
if(nums[j]==nums[i]){
count++;
if(count>half)
return nums[i];
}
}
}
return -1;
}
};


/*solution1 O(n^2) 20ms*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
int i=0,j=0,size=nums.size(),count=0;
int half=size/2;;
for(i=0;i<size;i++){
count=0;/*外循环每进行一次count计数变量应该重新置0*/
/*遇到有重复元素的，我们仅以最后一个元素做参照，来对该元素出现次数进行统计*/
while(nums[i]==nums[i+1])
i++;
for(j=0;j<size;j++){
if(nums[j]==nums[i]){
count++;
if(count>half)
return nums[i];
}
}
}
return -1;
}
};


1.sort

/*solution2 sort 40ms*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size()/2];
}
};



2.hash-table

hash-table的思路比较直接，维护一个unodered-map ,每次在hash-table里搜索nums[i]，搜索到则让以nums[i]为键值的元素加1即可，见代码:

/*solution4 use hash-table time-complexity O(n) memory-complexity O(n)*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.size()<2)
return nums[0];
unordered_map<int,int> num_count;
int i=0,size=nums.size();
for(i=0;i<size;i++){
if(num_count.find(nums[i])==num_count.end())
num_count[nums[i]]=0;
else
num_count[nums[i]]++;
if(num_count[nums[i]]>=size/2)
return nums[i];
}
return -1;
}
};



3.majority voting algorithm

The algorithm is carried out in two steps:

Eliminate all elements except one. Iterating through the array of numbers, maintain a current candidate and a counter initialized to 0. With the current element x in iteration, update the counter and (possibly) the candidate: if the counter is 0, set the current candidate to x and the counter to 1. If the counter is not 0, increment or decrement the counter based on whether x is the current candidate. Determine if the remaining element is a valid majority element. With the candidate acquired in step 1, iterate through the array of numbers and count its occurrences. Determine if the result is more than half of the sequence’s length. If so, the candidate is the majority. Otherwise, the sequence doesn’t contain a majority.

1. 不断删除数组中的元素直到仅剩下一个
2. 判断剩下的那一个是否真的是majority

class Solution {
public:
int majorityElement(vector<int>& nums) {
int curIndex=0,count=0,i=0;
for(i=0;i<nums.size();i++){
nums[curIndex]==nums[i]?count++:count--;
if(!count){
curIndex=i;
count=1;
}
}
return nums[curIndex];
}
};



### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017