Skip to content

Latest commit

 

History

History
257 lines (204 loc) · 5.69 KB

229.majority-element-ii.md

File metadata and controls

257 lines (204 loc) · 5.69 KB

题目地址(229. 求众数 II)

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

题目描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。   示例 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 -10^9 <= nums[i] <= 10^9

前置知识

  • 摩尔投票法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

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

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

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

实际上就是 0，1，2 三种可能。

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

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

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

229.majority-element-ii-1

229.majority-element-ii-1

关键点解析

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

代码

代码支持：CPP，JS, Java, Python

CPP Code:

classSolution { public: vector<int> majorityElement(vector<int>& nums) { int c1 = 0, c2 = 0, v1 = 0, v2 = 1; for (int n : nums) { if (v1 == n) ++c1; elseif (v2 == n) ++c2; elseif (!c1) v1 = n, ++c1; elseif (!c2) v2 = n, ++c2; else --c1, --c2; } c1 = c2 = 0; for (int n : nums) { if (v1 == n) ++c1; if (v2 == n) ++c2; } vector<int> v; if (c1 > nums.size() / 3) v.push_back(v1); if (c2 > nums.size() / 3) v.push_back(v2); return v; } };

JS Code：

/* * @lc app=leetcode id=229 lang=javascript * * [229] Majority Element II *//** * @param {number[]} nums * @return {number[]} */varmajorityElement=function(nums){constres=[];constlen=nums.length;letn1=null,n2=null,cnt1=0,cnt2=0;for(leti=0;i<len;i++){if(n1===nums[i]){cnt1++;}elseif(n2===nums[i]){cnt2++;}elseif(cnt1===0){n1=nums[i];cnt1++;}elseif(cnt2===0){n2=nums[i];cnt2++;}else{cnt1--;cnt2--;}}cnt1=0;cnt2=0;for(leti=0;i<len;i++){if(n1===nums[i]){cnt1++;}elseif(n2===nums[i]){cnt2++;}}if(cnt1>(len/3)>>>0){res.push(n1);}if(cnt2>(len/3)>>>0){res.push(n2);}returnres;};

Java Code：

/* * @lc app=leetcode id=229 lang=java * * [229] Majority Element II */classSolution { publicList<Integer> majorityElement(int[] nums) { List<Integer> res = newArrayList<Integer>(); if (nums == null || nums.length == 0) returnres; intn1 = nums[0], n2 = nums[0], cnt1 = 0, cnt2 = 0, len = nums.length; for (inti = 0; i < len; i++) { if (nums[i] == n1) cnt1++; elseif (nums[i] == n2) cnt2++; elseif (cnt1 == 0) { n1 = nums[i]; cnt1 = 1; } elseif (cnt2 == 0) { n2 = nums[i]; cnt2 = 1; } else { cnt1--; cnt2--; } } cnt1 = 0; cnt2 = 0; for (inti = 0; i < len; i++) { if (nums[i] == n1) cnt1++; elseif (nums[i] == n2) cnt2++; } if (cnt1 > len / 3) res.add(n1); if (cnt2 > len / 3 && n1 != n2) res.add(n2); returnres; } }

Python Code:

classSolution: defmajorityElement(self, nums): c1=c2=0v1=v2=-1fornuminnums: ifnum==v1: c1+=1elifnum==v2: c2+=1elifc1==0: c1=1v1=numelifc2==0: c2=1v2=numelse: c1-=1c2-=1# checkc1=c2=0fornuminnums: ifv1==num: c1+=1ifv2==num: c2+=1ans= [] ifc1>len(nums)//3: ans.append(v1) ifc2>len(nums)//3: ans.append(v2) returnlist(set(ans))

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(1)$

扩展

如果题目中 3 变成了 k，怎么解决？

大家可以自己思考一下，我这里给一个参考链接：https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!/64925

这个实现说实话不是很好，大家可以优化一下。

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

close