首页 > 代码库 > leetcode------Majority Element

leetcode------Majority Element

标题:Majority Element
通过率:33.8%
难度:简单

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.

 

这道题算是比较正常的算法题,一般的做法是排序,然后中间的那个数字一定是众数,本题可以变成不一定存在众数,排序算法的效率是O(nLogN)。本题我用的做法的效率是O(n)做法就是用一个栈来操作,若为空入栈,不为空,弹出比较,两元素相同则都入栈,两元素不同进行下一轮比较,这个做法效率非常高。

直接看代码:

 1 public class Solution { 2     public int majorityElement(int[] num) { 3         Stack<Integer> stack=new Stack<Integer>(); 4         int tmp=0; 5         int len=num.length; 6         for(int i=0;i<len;i++){ 7             if(stack.isEmpty()){ 8                 stack.push(num[i]); 9             }10             else{11                 tmp=stack.pop();12                 if(tmp==num[i])13                 {14                     stack.push(num[i]);15                     stack.push(tmp);16                 }17 18             }19         }20         tmp=stack.pop();21         return tmp;22     }23 }

 

leetcode------Majority Element