LintCode-46.主元素

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        // write your code
        /**
        * count: 统计当前认为的主元素的数量
        * seed: 当前认为的主元素
        * n: 数组长度
        **/
        int count = 0, seed = nums.get(0), n = nums.size();
        //从两头往中间循环
        for(int i = 1; i<n/2; i++){
            //若两数相等，主元素备选
            if(nums.get(i) == nums.get(n-i)){
                //若当前没有认为的主元素
                if(count == 0){
                    //那么取当前数为主元素
                    seed = nums.get(i);
                    //统计加一
                    count++;
                }
                //若已有认为的主元素
                else{
                    // 若与主元素相等，统计量加一
                    if(seed == nums.get(i)) count++;
                    // 若与主元素不等，统计量减一
                    // 这里如果减小到0了，可能会产生主元素切换
                    else count--;
                }
            }
        }
        //统计主元素出现的次数
        for(int i = 0;i<n;i++){
            if(nums.get(i) == seed){
                count++;
            }
        }
        //超过一半才被认为是主元素
        if(count >= n/2){
            return seed;
        }
        //提交了几次发现如果没超过一半需要返回最后的元素
        else{
            return nums.get(n-1);
        }
    }
}