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

 

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

  • 1 <= nums.length <= 5 * 104
  • -109 <= nums[i] <= 109

 

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

Related Topics
  • 数组
  • 哈希表
  • 计数
  • 排序

  • 👍 565
  • 👎 0

    • 简要思路就是：

    1. 留3个位置记录数字和次数，
    2. 挨个从头开始读，记录到步骤1的值里，如果数字相同累加，如果不同找个位子记下来
    3. 当凑满3个不同的数字的时候，所有数字统计数都减一
    4. 最后加进来的那个数字只有一个，所以最后那个数字个数变成了0，但是前面也是有可能有其他数字之前也只有一个，现在剩下0个的
    5. 把0个的数字占的位子清空，继续添加下一个数字，重复上面的操作，直到最后
    6. 剩下的两个数字中一定是有超过1/3的个数的
    7. 回去再遍历一遍，统计下数量，（为了省下其他数字数量统计的空间也是煞费苦心了），最后超过1/3的留下

    不好理解的话，我们换个角度。假如你有一根火腿肠，但是吃火腿肠的话有一个奇怪的习惯，需要把火腿肠分成N段，然后凑齐其中的3段，并排在一起，然后一起咬一块。

    大概就。。这样？一根长度为9的火腿肠（毕竟比较好除以3）

    此时你切成的N段火腿肠中，确保有一段是长度大于1/3的，那么思考一下，在每次都要拿着3段一起吃的情况下，即使你一直拿着那个大于1/3的那段，到最后这段也会生下来，毕竟到最后凑不出3段一起吃了。

    或者换个思路，除去最长的大于1/3的那段，剩下的总和是小于2/3的，那么这个2/3再分成两段的，最极限情况下，要保持3段的情况，这边分出来的也都是小于1/3的。

    最后剩余的情况
    剩下的数字并不一定的大于1/3的，还是上面的长度9的举例子，比如分成了4，3，2这样的长度组合的，3个一起进行消除，最后剩下的长度的2，1，所以还得回去再统计一遍，不过再统计的时候只需要统计剩下的两个数字的，如果是剩下1个，必然是大于1/3的。

    先决条件：需要保证给出的数组中一定存在数量超过1/3的数字

    那么在理解了思想的情况下这个之后，如果是类似的题目就基本都是这个套路能解决了

    代码

    class Solution {


    /**
     * 初始化了边界外的数值，表示一个空位子
     */
    int[] nums = {1000000001,1000000001,1000000001};

    int[] countArr = {0,0,0};

    public List<Integer> majorityElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            processNum(nums[i]);
        }

        //数量重新归零
        countArr[0] = 0;
        countArr[1] = 0;
        countArr[2] = 0;

        for (int i = 0; i < nums.length; i++) {
            //统计剩下的数字出现的次数
            countArr[0] += this.nums[0] == nums[i]?1:0;
            countArr[1] += this.nums[1] == nums[i]?1:0;
            countArr[2] += this.nums[2] == nums[i]?1:0;
        }
        
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < this.nums.length; i++) {
            //留下大于1/3的
            if (this.nums[i] < 1000000001 && countArr[i] > nums.length/3){
                list.add(this.nums[i]);
            }
        }

        return list;
    }

    public void processNum(int num){
        //是否是新插入的
        boolean insertFlag = false;
        for (int i = 0; i < 3; i++) {
            //原有有这个数字
            if (nums[i] == num){
                //数量加1
                countArr[i]++;
                insertFlag = true;
            }
        }
        //是原来不存在的数字，
        if (!insertFlag){
            for (int i = 0; i < 3; i++) {
                //找个空位子给安排下，并计数为1
                if (nums[i] == 1000000001){
                    nums[i] = num;
                    countArr[i] = 1;
                    break;
                }
            }
        }
        //如果没凑到3个数字，就继续往里一个新数字来处理
        if (countArr[0]==0 || countArr[1] == 0 || countArr[2]==0){
            return;
        }
        //如果是3个不同的数字，每个数字减一，
        // 并把剩余0的那个数字占的位子空出来
        for (int i = 0; i < 3; i++) {
            countArr[i]--;
            if (countArr[i]==0){
                nums[i] = 1000000001;
            }
        }
    }



}