1 题目描述
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.
2 分析
求主元素有两种O(n)量级的算法，一种是堆栈法，若栈为空或当前元素与栈顶元素相同，进栈，否则出栈。最后栈顶元素变为主元素。
另一种做法是芯片法，使用分治策略，比堆栈法要麻烦，主要是每次比较两个数字，不同，两个都扔掉，相同，留下一个，最后剩下的肯定是主元素。
3 代码
堆栈代码。
public int majorityElement(int[] num)
{
int majorrityElement = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < num.length; i++) {
if (stack.isEmpty()) {
stack.push(num[i]);
}else{
if (stack.peek() == num[i]) {
stack.push(num[i]);
}else {
stack.pop();
}
}
}
majorrityElement = stack.peek();
return majorrityElement;
}
芯片法有点麻烦，也没写。