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