题目地址
https://leetcode.com/problems/majority-element-ii/description/
题目描述
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]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
思路
这道题目和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; } }
扩展
如果题目中3变成了k,怎么解决?
大家可以自己思考一下,我这里给一个参考链接:https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!/64925
这个实现说实话不是很好,大家可以优化一下。
LeetCode题解169.majority-element题目地址 https://leetcode.com/problems/majority-element/description/ 题目描述 Given an array of size n, find the majority element. The majority element is the element that appears more tha…
LeetCode题解45.跳跃游戏 II给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解140. 单词拆分 II批注: 由于"可以重复使用字典中的单词", 因此稍微难一点定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明:分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入:s = "catsanddog"wordDict = […
LeetCode题解142. 环形链表 II为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。说明:不允许修改给定的链表。 示例 1:输入:head = [3,2,0,-4], pos = 1输出:tail connects to node index 1解释:链表中有一个环,其尾部连接到第二个节点。示例 2…
LeetCode题解213. 打家劫舍 II你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。示例 1:输入: [2,3…