LeetCode 之 JavaScript 解答第169题 —— 求众数 I（Majority El

hightopo 发布于2019-08-23 16:45 / 893人阅读

摘要：小鹿题目算法思路摩尔投票算法题目的要求是让我们求数组中超过一半数据以上相同的元素且总是存在的。

Time：2019/4/4
Title: Majority Element 1
Difficulty: easy
Author: 小鹿

题目：Majority Element 1

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

solve:

▉ 算法思路：摩尔投票算法

题目的要求是让我们求数组中超过一半数据以上相同的元素且总是存在的。有这样一个思路要和大家分享：

假如有这样一种数据，数组中的所存在的这个超过 n/2 以上的数据（众数）肯定比与此众数不相同的其他元素个数要多（n/2 以上）。我们可以这样统计，用一个变量来计数，另一个变量记录计数的该元素，遍历整个数组，如果遇到相同的 count 加 +1，不同的就 -1 ，最后所存储的就是众数，因为其他数据的个数比众数个数要少嘛，这就是所谓的摩尔投票算法。

▉ 代码实现：

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    //用来计数相同的数据
    let count = 0;
    //存储当前的元素
    let majority = 0;
    //遍历整个数组
    for(let i = 0;i < nums.length; ++i){
        //如果 count 为 0 
        if(count === 0){
            //将当前数据为众数
            majority = nums[i];
            count++;
        }else if(majority === nums[i]){
            //如果遍历的当前数据与存储的当前数据相同，计数+1
            count++;
        }else{
            //若不相同，计数 - 1
            count--;
        }
    }
     //假设相同的众数呢？
    if(count === 0){
        return -1;
    }else{
        return majority;
    }
};

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

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

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

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

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

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

摘要：继续使用摩投票算法，假设要投票，选取票数超过以上选为候选人，一个被分为三等份，也就是说最多有两位当选人。排序解决先进行一次排序快排，然后遍历数据，找出满足条件的数据。 Time：2019/4/5Title: Majority Element 2Difficulty: mediumAuthor: 小鹿问题：Majority Element 2 Given an integer ar...

BearyChat 2019-08-23 16:45 评论0 收藏0
LeetCode 攻略 - 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
LeetCode 攻略 - 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
leetcode 169 Majority Element

摘要：因为众数出现的次数必定大于，所以我们只要取第个位置上的元素，这个元素一定为我们要找的众数。题目详情 Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.You may assume th...

tangr206 2019-08-15 13:53 评论0 收藏0
[Leetcode] Majority Element 众数

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

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