本文共 1430 字，大约阅读时间需要 4 分钟。

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]

Input: [1,1,1,3,3,2,2,2]

来源：力扣（LeetCode）

找出出现次数大于n/3的数。

结果肯定是一个或者两个。

先选出两个候选者，再判断它出现的次数是否满足。

class Solution {    public List
   
     majorityElement(int[] nums) {        int a = 0;        int b = 0;        int counta = 0;        int countb = 0;        for (int i = 0; i < nums.length; i++) {            if (nums[i] == a) {                counta++;            } else if (nums[i] == b) {                countb++;            } else if (counta == 0) {                a = nums[i];                counta++;            } else if (countb == 0) {                b = nums[i];                countb++;            } else {                counta--;                countb--;            }        }        counta = 0;        countb = 0;        for (int i = 0; i < nums.length; i++) {            if (nums[i] == a) {                counta++;            } else if (nums[i] == b) {                countb++;            }        }        List 
    
      ans = new ArrayList<>();        if (counta > nums.length / 3) {            ans.add(a);        }        if (countb > nums.length / 3) {            ans.add(b);        }        return ans;    }}