Majority Element

Majority Element 

问题：

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.

思路：

　　超过半数的总会剩余

我的代码：

public class Solution {
    public int majorityElement(int[] num) {
        if(num == null || num.length == 0)  return -1;
        Stack<Integer> stack = new Stack<Integer>();
        for(int i = 0; i < num.length; i++)
        {
            if(stack.isEmpty()) stack.push(num[i]);
            else
            {
                int top = stack.peek();
                if(top == num[i])   stack.push(num[i]);
                else    stack.pop();
            }
        }
        return stack.pop();
    }
}

他人代码：

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

学习之处：

• 思路相似，我的方法空间复杂度O(n) 他人方法O(1) 
• maj 保存的是到目前扫描为止，发现的最大值，要不要更新最大值看count是否为0

need to learn