資訊專欄INFORMATION COLUMN
摘要：小鹿題目算法思路摩爾投票算法題目的要求是讓我們求數(shù)組中超過一半數(shù)據(jù)以上相同的元素且總是存在的。
Time：2019/4/4
Title: Majority Element 1
Difficulty: easy
Author: 小鹿
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: 2solve:
題目的要求是讓我們求數(shù)組中超過一半數(shù)據(jù)以上相同的元素且總是存在的。有這樣一個思路要和大家分享：假如有這樣一種數(shù)據(jù)，數(shù)組中的所存在的這個超過 n/2 以上的數(shù)據(jù)（眾數(shù)）肯定比與此眾數(shù)不相同的其他元素個數(shù)要多（n/2 以上）。我們可以這樣統(tǒng)計，用一個變量來計數(shù)，另一個變量記錄計數(shù)的該元素，遍歷整個數(shù)組，如果遇到相同的 count 加 +1，不同的就 -1 ，最后所存儲的就是眾數(shù)，因?yàn)槠渌麛?shù)據(jù)的個數(shù)比眾數(shù)個數(shù)要少嘛，這就是所謂的摩爾投票算法。
/**
* @param {number[]} nums
* @return {number}
*/
var majorityElement = function(nums) {
//用來計數(shù)相同的數(shù)據(jù)
let count = 0;
//存儲當(dāng)前的元素
let majority = 0;
//遍歷整個數(shù)組
for(let i = 0;i < nums.length; ++i){
//如果 count 為 0
if(count === 0){
//將當(dāng)前數(shù)據(jù)為眾數(shù)
majority = nums[i];
count++;
}else if(majority === nums[i]){
//如果遍歷的當(dāng)前數(shù)據(jù)與存儲的當(dāng)前數(shù)據(jù)相同，計數(shù)+1
count++;
}else{
//若不相同，計數(shù) - 1
count--;
}
}
//假設(shè)相同的眾數(shù)呢？
if(count === 0){
return -1;
}else{
return majority;
}
};
歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/103244.html
摘要：繼續(xù)使用摩投票算法，假設(shè)要投票，選取票數(shù)超過以上選為候選人，一個被分為三等份，也就是說最多有兩位當(dāng)選人。排序解決先進(jìn)行一次排序快排，然后遍歷數(shù)據(jù)，找出滿足條件的數(shù)據(jù)。 Time：2019/4/5Title: Majority Element 2Difficulty: mediumAuthor: 小鹿 問題：Majority Element 2 Given an integer ar...
摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：因?yàn)楸姅?shù)出現(xiàn)的次數(shù)必定大于，所以我們只要取第個位置上的元素，這個元素一定為我們要找的眾數(shù)。 題目詳情 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...
摘要：排序法復(fù)雜度時間空間思路將數(shù)組排序，這時候數(shù)組最中間的數(shù)肯定是眾數(shù)。投票法復(fù)雜度時間空間思路記錄一個變量，還有一個變量，開始遍歷數(shù)組。代碼投票法復(fù)雜度時間空間思路上一題中，超過一半的數(shù)只可能有一個，所以我們只要投票出一個數(shù)就行了。 Majority Element I Given an array of size n, find the majority element. The m...
閱讀 1020·2021-11-15 18:06
閱讀 2386·2021-10-08 10:04
閱讀 2673·2019-08-28 18:03
閱讀 923·2019-08-26 13:42
閱讀 1943·2019-08-26 11:31
閱讀 2447·2019-08-23 17:13
閱讀 951·2019-08-23 16:45
閱讀 2081·2019-08-23 14:11
