You want to know if there is a value that is present in the list for more than half of the elements in that list. If so what is that value? If not, you need to know that there is no majority element.
Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Step 0: Initialize count to be zero
Step 1: Go through the vote
i. Check if the count is zero
if so then assign the c to this vote's candidate and then set count=1
if not then check if this vote's candidate is equal to c
if yes then set count+=1
if no then set count-=1
Step 2: Continue until the end
Step 3: Now, return c
Step 4: Check once again by going through the votes if it is really the majority.
int count_vote(int a[],int size)
{
int count=0,c,i;
for(i=0;i<size;i++)
{
if(count==0)
{
c=a[i];
count=1;
}
else
{
if(c==a[i])
count++;
else
count--;
}
}
return c;
}
majority=count_vote(a,size);
for(i=0;i<size;i++)
if(a[i]==majority)
count++;
if(count>size/2)
Also check code from https://gist.github.com/devhary/1085114
http://www.geeksforgeeks.org/majority-element/
METHOD 2 (Using Binary Search Tree) )(nlogn) ==> BST: A frequently used data structure
Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
If a self-balancing-binary-search tree is used then O(nlogn)
http://massivealgorithms.blogspot.com/2014/11/finding-majority-element-in-unsorted.html
方法1：类似于消除原理，既然某个数字大于长度的一半，那么我们就遍历数组，如果两个数不相等则消除，最后剩下的数就是我们要的。当然如果不存在这样的数，这是不行的。所以最后要再遍历一遍验证这个数的出现次数是否大于数组的一半。
方法2：用qsort的partition的方法找出第k大数，k就是数组中间的数，对于n为偶数是中间两个的任意一个数，奇数的话就只有一个。那么，因为数的个数超过一半，那么中间那个数肯定是超过一半的那个数，否则这个数就不存在了。最后遍历一遍数组来验证一下。partition的平摊复杂度为O(n)。最后算法总体复杂度O(n)
http://segmentfault.com/a/1190000003972762
public static int getCandidate(int[] array) {
int majority = 0;
int count = 0;
for (int n : array) {
if (count == 0) {
majority = n;
}
if (n == majority) {
count++;
} else {
count--;
}
}
return majority;
}
public static int findMajorityElement(int[] array) {
int candidate = getCandidate(array);
return validate(array, candidate) ? candidate : -1;
}
public static boolean validate(int[] array, int majority) {
int count = 0;
for (int n : array) {
if (n == majority) {
count++;
}
}
return count > array.length / 2;
}
public static int findMajorityElement(int[] array) {
for (int x : array) {
if (validate(array, x)) {
return x;
}
}
return -1;
}
Read full article from Gregable: Majority Voting Algorithm - Find the majority element in a list of values
Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Boyer-Moore Algorithm
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
2. Check if the element obtained from above step is majority element.
1. Finding a Candidate:
Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.
Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]
Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.
http://www.geeksforgeeks.org/majority-element/
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;}
The Boyer-Moore algorithm is presented in this paper: Boyer-Moore Majority Vote Algorithm. The algorithm uses O(1) extra space and O(N) time. It requires exactly 2 passes over the input list
http://pandeyece.blogspot.com/2013/01/a-fast-majority-vote-algorithm-moores.htmlStep 0: Initialize count to be zero
Step 1: Go through the vote
i. Check if the count is zero
if so then assign the c to this vote's candidate and then set count=1
if not then check if this vote's candidate is equal to c
if yes then set count+=1
if no then set count-=1
Step 2: Continue until the end
Step 3: Now, return c
Step 4: Check once again by going through the votes if it is really the majority.
int count_vote(int a[],int size)
{
int count=0,c,i;
for(i=0;i<size;i++)
{
if(count==0)
{
c=a[i];
count=1;
}
else
{
if(c==a[i])
count++;
else
count--;
}
}
return c;
}
majority=count_vote(a,size);
for(i=0;i<size;i++)
if(a[i]==majority)
count++;
if(count>size/2)
Also check code from https://gist.github.com/devhary/1085114
http://www.geeksforgeeks.org/majority-element/
METHOD 2 (Using Binary Search Tree) )(nlogn) ==> BST: A frequently used data structure
Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
If a self-balancing-binary-search tree is used then O(nlogn)
http://massivealgorithms.blogspot.com/2014/11/finding-majority-element-in-unsorted.html
方法1：类似于消除原理，既然某个数字大于长度的一半，那么我们就遍历数组，如果两个数不相等则消除，最后剩下的数就是我们要的。当然如果不存在这样的数，这是不行的。所以最后要再遍历一遍验证这个数的出现次数是否大于数组的一半。
方法2：用qsort的partition的方法找出第k大数，k就是数组中间的数，对于n为偶数是中间两个的任意一个数，奇数的话就只有一个。那么，因为数的个数超过一半，那么中间那个数肯定是超过一半的那个数，否则这个数就不存在了。最后遍历一遍数组来验证一下。partition的平摊复杂度为O(n)。最后算法总体复杂度O(n)
http://segmentfault.com/a/1190000003972762
1.1 排序
结论很简单：排序完之后，主要元素必然在下标
n/2的位置。1.2 位操作
这里设int为32位整数。我们对这些数以二进制的形式，逐位观察，尝试构造出主要元素来。对32位中的每一位，如果1占多数，则主要元素的对应位为1，否则为0。
public int majorityElement(int[] nums) {
int res=0,major=nums.length/2;
for (int i=31;i>=0;i--){
int pos=0;
for(int n:nums)
pos+=(n>>i)&1;
pos=pos>major? 1:0;
res|=pos<<i;
}
return res;
}2. Boyer-Moore算法
比较直观的解释：在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。def majorityElement(self, nums):
count,major=0,0
for n in nums:
if count==0:
major=n
if major==n:
count+=1
else:
count-=1
return majorpublic static int getCandidate(int[] array) {
int majority = 0;
int count = 0;
for (int n : array) {
if (count == 0) {
majority = n;
}
if (n == majority) {
count++;
} else {
count--;
}
}
return majority;
}
public static int findMajorityElement(int[] array) {
int candidate = getCandidate(array);
return validate(array, candidate) ? candidate : -1;
}
int count = 0;
for (int n : array) {
if (n == majority) {
count++;
}
}
return count > array.length / 2;
}
public static int findMajorityElement(int[] array) {
for (int x : array) {
if (validate(array, x)) {
return x;
}
}
return -1;
}
Read full article from Gregable: Majority Voting Algorithm - Find the majority element in a list of values
