求众数 II

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii

题目描述:

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：[3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

思路:

• 对数组进行排序
• 遍历数组的过程中判断nums[i] == nums[i + 1]，当前元素和下一个元素是否相等
• • 相等：记录当前元素重复的数量,idx++
• • 不相等: 判断当前元素nums[i]重复的数量是否超过[n / 3].
• • • 是,记录到结果集合.重置idx
• • • 否,直接重置idx

对于数组最后的元素满足要求的情况,例如[1,3,3,3,3,3]，到结束为止，都没有和元素3不相等的元素.因此需要额外再添加一个判断idx是否大大[n / 3]，是的话，将最后的元素添加到结果集合.

代码实现:

class Solution {
    public List<Integer> result = new ArrayList();
    public List<Integer> majorityElement(int[] nums) {
        
        Arrays.sort(nums);

        int len = nums.length;
        int count = len / 3;

        if (len == 1) {
            result.add(nums[0]);
            return result;
        } else if (len == 2) {
            result.add(nums[0]);
            if (nums[0] != nums[1]) result.add(nums[1]);
            return result;
        }

        int idx = 1;
        for (int i = 0; i < len - 1; i++) {
            if (nums[i] == nums[i + 1]) idx++;
            else {
                // 符合要求.
                if (idx > count) result.add(nums[i]);
                idx =  1;
            }     
        }
        // 数组最后的数符合要求.
        if (idx > count) result.add(nums[len - 1]);
        
        return result;
    }
}