你的位置:首页 > Java教程

[Java教程]229. Majority Element II


Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

代码如下:(方法一:超内存)

 1 public class Solution { 2   public List<Integer> majorityElement(int[] nums) { 3     List<Integer> list=new ArrayList<>(); 4     if(nums.length==0) 5     return list; 6     Arrays.sort(nums); 7     int[] a=new int[nums[nums.length-1]+1]; 8      9     for(int i=0;i<nums.length;i++)10       a[nums[i]]++;11       12     for(int i=0;i<nums.length;)13     {14       if(a[nums[i]]>nums.length/3)15       {16         list.add(nums[i]);17         i=i+a[nums[i]]-1;18       }19     }20    21     22     return list;23   }24 }