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; }
芯片法有点麻烦，也没写。
[Leedcode 169]Majority Element
原文：http://www.cnblogs.com/lingtingvfengsheng/p/4182869.html