class Solution {
    public int moreThanHalfNum_Solution(int[] a) {
        if (a.length == 1) return a[0];
        a[0] = a[0] == a[1] ? 2 : 1;
        for (int i = 2; i < a.length; ++i){
           if (a[i] == a[i-1]) ++a[0];
           else {
               if (--a[0] < 0) a[0] = 1;
               else a[i] = a[i-1];
           }
       }
       return a[a.length - 1];
    }
}