LeetCode 之 JavaScript 解答第169題 —— 求眾數 I（Majority El

hightopo 發布于2019-08-23 16:45 / 915人閱讀

摘要：小鹿題目算法思路摩爾投票算法題目的要求是讓我們求數組中超過一半數據以上相同的元素且總是存在的。

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算法題匯編語言程序設計第二版課后題答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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