【LeetCode-数组】求众数 II
2021-02-02 01:17
标签:说明 logs 示例 时间复杂度 不能 problem 题目 描述 for 给定一个大小为 n 的数组,找出其中所有出现超过 ? n/3 ? 次的元素。 题目链接: https://leetcode-cn.com/problems/majority-element-ii/ 要求算法的时间复杂度为 O(n),空间复杂度为 O(1),所以排序和哈希表的算法都不能用了。这题使用和多数元素类似的投票法。 代码如下: 1、https://leetcode-cn.com/problems/majority-element-ii/solution/169ti-sheng-ji-ban-xiang-jie-zhu-xing-jie-shi-tong/ 【LeetCode-数组】求众数 II 标签:说明 logs 示例 时间复杂度 不能 problem 题目 描述 for 原文地址:https://www.cnblogs.com/flix/p/12812160.html题目描述
说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。
示例:输入: [3,2,3]
输出: [3]
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
做这题之前要先做一下多数元素。思路
超过n/3的元素一定不超过2个。我们将这两个数字记为candi1和candi2,对应的票数分别为cnt1和cnt2。算法如下:
class Solution {
public:
vector
参考
上一篇:C++ 正则