Majority Element II

Total Accepted: 3172

Total Submissions: 14746

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.

[思路]

[REFERENCE] http://bookshadow.com/weblog/2015/06/29/leetcode-majority-element-ii/

观察可知。数组中至多可能会有2个出现次数超过 ⌊ n/3 ⌋ 的众数

记变量n1, n2为候选众数； c1, c2为它们相应的出现次数

遍历数组。记当前数字为num

若num与n1或n2同样，则将其相应的出现次数加1

否则，若c1或c2为0。则将其置为1。相应的候选众数置为num

否则，将c1与c2分别减1

最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。

[CODE]

public class Solution {    public List
     
       majorityElement(int[] nums) {        // 1, 2        List
      
        res = new ArrayList<>();        if(nums==null || nums.length==0) return res;        if(nums.length==1) {            res.add(nums[0]);            return res;        }                int m1 = nums[0];        int m2 = 0;                int c1 = 1;        int c2 = 0;                for(int i=1; i
       
        nums.length/3) res.add(m1);        if(c2>nums.length/3) res.add(m2);        return res;    }}