# O(n) time O(1) space fastest solution

• ``````public class Solution {
public int majorityElement(int[] num) {

int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;

}
return major;
}
}``````

• Genius algorithm. It took me a few minutes to discover how it exactly works.

• Genius, That's really clever!!!

• This is not complete. You need to check if "major" is really a majority element.

• how does this work?

• This post is deleted!

• The question "Majority Element" is amphibolous, because a precondition that the given array must be sorted is not mentioned!

• Excellent solution. Much better if we check count>=length/2 int the loop?

• Brilliant algorithm!

• No, this solution doesn't require the given array be sorted.

• Genius，Genius， Genius！

• Seriously? does this really work?
if I input {3,3,4,6,7}, it returns 7, instead of 3....

• ok, got it. it's trick. An assumption is the frequency of majority element > n/2

• can anyone give the exact definition of "cnt"

• it works when majority number is exist.

• excellent solution!

• If the poster could really be that smart to figure out this algorithm by him/her-self, this would be a top top conference paper and bring him/her to a professor position. Absolutely no need to struggle coding here.

Should cite the source:

Boyer-Moore Majority Vote Algorithm

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

• This post is deleted!

• ``````public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
return nums[len/2];
}
}``````

• got it,It's so good,my solution is like yours, I also used Arrays.sort(nums); but your solution is more Simple and efficient.Here is mine:

``````public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int maj=0;
for(int i=0;i<nums.length/2+1;i++){
if(nums[i]==nums[i+nums.length/2]){
maj=nums[i];
break;
}
}
return maj;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.