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.

解法:

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

public class Solution {    public int majorityElement(int[] num) {    	int sum=0;    	int result=0;    	for(int i=0;i<num.length;i++){    		if(sum==0){    			result=num[i];    			sum++;    		}    		else if(result==num[i]){    			sum++;    			if(sum>num.length/2){    				return result;    			}    		}    		else sum--;    	}    	return result;    }}

leetcode majority elements