# Majority Voting Algorithm

The algorithm is carried out in two steps:

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

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

JAVA实现如下:

public int majorityElement(int[] num) {
int n = num.length;
int candidate = num[0], counter = 0;
for (int i : num) {
if (counter == 0) {
candidate = i;
counter = 1;
} else if (candidate == i) {
counter++;
} else {
counter--;
}
}

counter = 0;
for (int i : num) {
if (i == candidate) counter++;
}
if (counter <= n / 2) return -1;
return candidate;

}

# 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) {
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];
}
};

# 229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?

Do you have a better hint?

class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int curIndex1=0,curIndex2=0,count1=0,count2=0;
int size=nums.size(),i=0,tri=size/3;
vector<int>res;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
else if(!count1){
count1=1;
curIndex1=i;
}
else if(!count2){
count2=1;
curIndex2=i;
}
else{
count1--;
count2--;
}
}
count1=0;
count2=0;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
}
if(count1>tri)
res.push_back(nums[curIndex1]);
if(count2>tri)
res.push_back(nums[curIndex2]);
return res;
}
};

### 学籍管理系统文档

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

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017