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;
}
芯片法有点麻烦,也没写。