前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【每日算法Day 91】求解数组中出现次数超过1/3的那个数

【每日算法Day 91】求解数组中出现次数超过1/3的那个数

作者头像
godweiyang
发布2020-04-14 15:20:13
6960
发布2020-04-14 15:20:13
举报
文章被收录于专栏:算法码上来
题目链接

LeetCode 229. 求众数 II[1]

题目描述

给定一个大小为 的数组,找出其中所有出现超过 次的元素。

说明:

  • 要求算法的时间复杂度为 ,空间复杂度为 。

示例1

代码语言:javascript
复制
输入:
[3,2,3]
输出:
3

示例2

代码语言:javascript
复制
输入:
[1,1,1,3,3,2,2,2]
输出:
[1,2]

题解

这是求解众数的升级版: 【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数[2]但是这题没有保证一定存在满足条件的数,不过不要紧。

首先可以肯定最多有两个数的数量超过 1/3 ,这个就不用我过多解释了吧。然后我们只需要找出出现次数最多的两个数,看它俩次数是否超过 1/3 就行了。

那么怎么找呢?如果存在某个数超过 1/3 ,那我们每次删掉三个不同的数,直到最后没法删,最后剩下的数一定有这个超过 1/3 的数。原因很简单,因为每删一次最多删掉一个这个数,而删除最多 1/3 数组长度次之后所有数都被删光了,但是这个数还剩下一点。

所以我们用两个变量 cand1cand2 表示两个候选人,cnt1cnt2 表示两个候选人数量。那么如果两个候选人有一个和当前数 x 相同,对应的数量就加一。否则的话如果如果有某个候选人为空,就让 x 顶替成为新的候选人。否则的话就说明两个候选人都有,并且 x 和它俩都不相同,那么就同时删除三个不同的数,也就是两个候选人数量各减一,同时删去 x

最后判断两个候选人数量是否超过了 1/3 就行了。

这里关键点就在于,每次删除三个不同的数,判断最后剩下的数是否符合题意就行了

代码

c++

代码语言:javascript
复制
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        int cand1 = 0, cand2 = 0, cnt1 = 0, cnt2 = 0;
        for (auto x : nums) {
            if (cand1 == x) {
                cnt1++;
            } else if (cand2 == x) {
                cnt2++;
            } else if (!cnt1) {
                cand1 = x;
                cnt1++;
            } else if (!cnt2) {
                cand2 = x;
                cnt2++;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1 = cnt2 = 0;
        for (auto x : nums) {
            if (x == cand1) cnt1++;
            else if (x == cand2) cnt2++;
        }
        vector<int> res;
        if (cnt1 > n/3) res.push_back(cand1);
        if (cnt2 > n/3) res.push_back(cand2);
        return res;
    }
};

python

代码语言:javascript
复制
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        cand1, cand2, cnt1, cnt2 = 0, 0, 0, 0
        for x in nums:
            if cand1 == x:
                cnt1 += 1
            elif cand2 == x:
                cnt2 += 1
            elif cnt1 == 0:
                cand1 = x
                cnt1 = 1
            elif cnt2 == 0:
                cand2 = x
                cnt2 = 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        cnt1 = cnt2 = 0
        for x in nums:
            if x == cand1:
                cnt1 += 1
            elif x == cand2:
                cnt2 += 1
        res = []
        if cnt1 > n//3:
            res.append(cand1)
        if cnt2 > n//3:
            res.append(cand2)
        return res

参考资料

[1]

LeetCode 229. 求众数 II: https://leetcode-cn.com/problems/majority-element-ii/

[2]

【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数: https://godweiyang.com/2020/04/04/leetcode-inteview-39/

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-04-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法码上来 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题解
  • 代码
    • c++
      • python
        • 参考资料
        相关产品与服务
        NLP 服务
        NLP 服务(Natural Language Process,NLP)深度整合了腾讯内部的 NLP 技术,提供多项智能文本处理和文本生成能力,包括词法分析、相似词召回、词相似度、句子相似度、文本润色、句子纠错、文本补全、句子生成等。满足各行业的文本智能需求。
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档