首页 > 代码库 > [Leedcode 169]Majority Element
[Leedcode 169]Majority Element
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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。