LeetCode 之 JavaScript 解答第229题 —— 求众数 II（Majority E

BearyChat 发布于2019-08-23 16:45 / 2610人阅读

摘要：继续使用摩投票算法，假设要投票，选取票数超过以上选为候选人，一个被分为三等份，也就是说最多有两位当选人。排序解决先进行一次排序快排，然后遍历数据，找出满足条件的数据。

Time：2019/4/5
Title: Majority Element 2
Difficulty: medium
Author: 小鹿

问题：Majority Element 2

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]

solve:

▉ 算法思路：

1、上一篇是一个求超过 n/2 个数的数，采取的是用一个计数变量和计数元素变量来完成的。本篇题目是超过 n/3 的个数，我们分别用两个变量来完成，条件限制是时间复杂度是O(n),空间复杂度为O(1)。

2、继续使用摩投票算法，假设要投票，选取票数超过 n/3 以上选为候选人，一个 n 被分为三等份，也就是说最多有两位当选人。

3、假设第一个人投甲，第二个投乙，甲、乙都站到台上各个计数为 1 ，随之第三个投甲，第四个投乙，计数分别加 1 ，第五个投丙，因为只有两个台子，所以那就让甲乙票数计数各减 1 ，当甲、乙的票数分别减到 0 之后，第 m 个人投丙，就让丙代替甲或已，继续遍历数据，直到遍历完成为止。

4、上述只选择出了那些有可能满足条件的数据，下面对cm、cn存储的数据做验证。

▉ 其他解法：

如果没有题目中时间复杂度和空间复杂度的限制，有多种解决方法：

1、散列表解决：先遍历一遍数据，统计每个数字出现的次数，然后再遍历一遍散列表，找出满足条件的数字。时间复杂度为O(n)，空间复杂度为 O(n)。

2、排序解决：先进行一次排序（快排），然后遍历数据，找出满足条件的数据。时间复杂度为O(nlogn)，空间复杂度为O(1)。

▉ 代码实现：

      /**
        * @param {number[]} nums
        * @return {number[]}
        */
        var majorityElement = function(nums) {
            let [m,n,cm,cn,countm,countn] = [0,0,0,0,0,0];
            let result = [];
            
            for(let i = 0;i < nums.length; ++i){
                //m === nums[i]和n === nums[i]的判断一定放到 cm === 0 和 cn === 0 之前，负责产生 bug。
                if(m === nums[i]){
                    cm ++;
                }else if(n === nums[i]){
                    cn ++;
                }else if(cm === 0){
                    m = nums[i];
                    cm ++;
                }else if(cn === 0){
                    n = nums[i];
                    cn ++;
                }else{
                    cn--;
                    cm--;
                }
            }
            //验证 cm、cn 存储的数据
            for(let index in nums){
                if(nums[index] === m){
                    ++countm;
                }
                if(nums[index] === n){
                    ++countn;
                }
            }
            
            if(countm > Math.floor(nums.length/3)){
                result.push(m);
            }
        
            if(countn > Math.floor(nums.length/3) && n != m){
                result.push(n);
            }
            return result;
        };

        //测试
        let arr =[1,2,2,3,2,1,1,3];
        console.log(majorityElement(arr));

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

欢迎关注我个人公众号：「一个不甘平凡的码农」，记录了自己一路自学编程的故事。

GPU服务器云服务器 c语言数据求众数如何用c语言求众数 javascript算法题汇编语言程序设计第二版课后题答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103243.html

LeetCodeem> 之 JavaScriptem> 解答第169题 —— 求众数 I（Majorityem> El

摘要：小鹿题目算法思路摩尔投票算法题目的要求是让我们求数组中超过一半数据以上相同的元素且总是存在的。 Time：2019/4/4Title: Majority Element 1Difficulty: easyAuthor: 小鹿题目：Majority Element 1 Given an array of size n, find the majority element. The ...

hightopo 2019-08-23 16:45 评论0 收藏0
LeetCodeem> 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCodeem> 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
第7期 Datawhale 组队学习计划

马上就要开始啦这次共组织15个组队学习涵盖了AI领域从理论知识到动手实践的内容按照下面给出的最完备学习路线分类难度系数分为低、中、高三档可以按照需要参加 - 学习路线 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 评论0 收藏0
[Leetcodeem>] Majorityem> Element 众数

摘要：排序法复杂度时间空间思路将数组排序，这时候数组最中间的数肯定是众数。投票法复杂度时间空间思路记录一个变量，还有一个变量，开始遍历数组。代码投票法复杂度时间空间思路上一题中，超过一半的数只可能有一个，所以我们只要投票出一个数就行了。 Majority Element I Given an array of size n, find the majority element. The m...

sihai 2019-08-14 12:29 评论0 收藏0