229. 求众数 II

lucifer210

发布于 2019-08-16 14:59:40

7670

发布于 2019-08-16 14:59:40

文章被收录于专栏：脑洞前端脑洞前端脑洞前端

题目地址

https://leetcode.com/problems/majority-element-ii/description/

题目描述

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

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

输入: [3,2,3]
输出: [3]
示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题目和169.majority-element 很像。

我们仍然可以采取同样的方法 - “摩尔投票法”，具体的思路可以参考上面的题目。

但是这里有一个不同的是这里的众数不再是超过 1/2,而是超过 1/3。题目也说明了，超过三分之一的有可能有多个（实际上就是0，1，2三种可能）。

因此我们不能只用一个counter来解决了。我们的思路是同时使用两个counter，其他思路和上一道题目一样。

最后需要注意的是两个counter不一定都满足条件，这两个counter只是出现次数最多的两个数字。有可能不满足出现次数大于1/3，因此最后我们需要进行过滤筛选。

这里画了一个图，大家可以感受一下：

关键点解析

摩尔投票法
两个counter
最后得到的只是出现次数最多的两个数字，有可能不满足出现次数大于1/3

代码

JavaScript代码：

/*
 * @lc app=leetcode id=229 lang=javascript
 *
 * [229] Majority Element II
 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var majorityElement = function(nums) {
  const res = [];
  const len = nums.length;
  let n1 = null,
    n2 = null,
    cnt1 = 0,
    cnt2 = 0;

  for (let i = 0; i < len; i++) {
    if (n1 === nums[i]) {
      cnt1++;
    } else if (n2 === nums[i]) {
      cnt2++;
    } else if (cnt1 === 0) {
      n1 = nums[i];
      cnt1++;
    } else if (cnt2 === 0) {
      n2 = nums[i];
      cnt2++;
    } else {
      cnt1--;
      cnt2--;
    }
  }

  cnt1 = 0;
  cnt2 = 0;

  for (let i = 0; i < len; i++) {
    if (n1 === nums[i]) {
      cnt1++;
    } else if (n2 === nums[i]) {
      cnt2++;
    }
  }

  if (cnt1 > (len / 3) >>> 0) {
    res.push(n1);
  }
  if (cnt2 > (len / 3) >>> 0) {
    res.push(n2);
  }

  return res;
};

Java代码：

/*
 * @lc app=leetcode id=229 lang=java
 *
 * [229] Majority Element II
 */
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0)
            return res;
        int n1 = nums[0], n2 = nums[0], cnt1 = 0, cnt2 = 0, len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == n1)
                cnt1++;
            else if (nums[i] == n2)
                cnt2++;
            else if (cnt1 == 0) {
                n1 = nums[i];
                cnt1 = 1;
            } else if (cnt2 == 0) {
                n2 = nums[i];
                cnt2 = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1 = 0;
        cnt2 = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == n1)
                cnt1++;
            else if (nums[i] == n2)
                cnt2++;
        }
        if (cnt1 > len / 3)
            res.add(n1);
        if (cnt2 > len / 3 && n1 != n2)
            res.add(n2);
        return res;
    }
}