【解题报告】lintcode46主元素

题意

给出一组数字，其中某个数字占据了总数的1/2以上，就是主元素，找出它 o（n）复杂度

思路

使用贪心的思路，每次从数组中拿一个数字，就认为它是主元素，然后继续拿，如果不同，就把计数器减一，如果相同，就把计数器加一，当计数器到0,就把下一个数字又作为主元素，继续这个过程，到最后，拿在手上的就是主元素了。

例子

比如数组[1,2,2,2,1,1,1] 开始时，设置主元素为1，计数器为1 2 与 1 不同，计数器减一，为0 由于计数为0， 取下一个数为主元素，2 继续，下个仍然是2，计数器加一 下个数是1， 计数减一， 设1为主元素 剩下两个1 最后我们的主元素就是手上的1

代码

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: find a  majority number
     */
       public int majorityNumber(ArrayList<Integer> nums) {
        // write your code
        int count = 1,major = nums.get(0);
        for (int i =1;i<nums.size();i++){
            if (count == 0){
                major = nums.get(i);
                count = 0;
            }
            else if (nums.get(i) !=  major){
                count--;
            }else if (nums.get(i) == major){
                count++;
            }

        }
        return major;
    }
}