如何理解摩爾投票演算法？

1樓：致知

來乙個理解起來更簡單的~

假設有乙個擂台，有一組人，每個人有編號，相同編號為一組，依次上場，沒人時上去的便是擂主（x），若有人，編號相同則繼續站著（台上總人數+1），若不同，假設每個人戰鬥力相同，都同歸於盡，則台上總人數-1；那麼到最後站著的肯定是人數佔絕對優勢的那一組啦~對應的編號就是答案

class

Solution

:def

majorityElement

(self

,nums

:List

[int

])->

int:

votes=0

fornum

innums://

每乙個人都要出來挑戰

ifvotes==0

://擂台上沒人

選乙個出來當擂主

x就是擂主

votes就是台上的人數x=

numvotes+=1

ifnum==x

else-1

//如果是自己人就站著唄

如果不是

就同歸於盡人數-

1returnx

2樓：李智

摩爾投票演算法的核心是前提：求多數元素（可以是多於一半，三分之一，四分之一...）

下面已半數為例

var majorityElement = function(nums)

演算法分3步。

假設第乙個數是結果，並給它算出現次數

迴圈發現相同數計數加一，不同則計數減一。

當計數等於 0 時，換當前出現的數，並重新計數

迴圈結束，剩下的數就位結果返回

首先，結果在上次發生重新計數後，次數出現多餘剩餘數的一半。

並且有前提，陣列總是存在多數元素，那麼已任意位置開始數，結果都會多於一般。所以摩爾投票法成立。

這個演算法關鍵在於特殊的前提陣列總是存在多數元素，如果不一定存在，那麼返回結果就不正確，需要對結果進行核對結果是否多於半數

3樓：李萌

如何贏得一場足球比賽？

答：比對方多進乙個(或好幾個)

注：你就是那個眾數對手就是其他數，整個陣列就是一場比賽的進球時間點

4樓：feature

求主要元素，陣列中佔比超過一半的元素稱之為主要元素。給定乙個整數陣列，找到它的主要元素。若沒有，返回-1

class

Solution

:def

majorityElement

(self

,nums

:List

[int

])->

int:n=

len(

nums

)major

=nums[0

]# major記錄不能抵消的數字

count=1

# count記錄不能抵消的數字的個數，初始情況：nums中的第乙個數無法抵消，故count=1i=

1while

ifnums[i

]!=major

:# 抵消條件

count-=1

ifi+1

count

<1:

# 修改major的條件，count < 1即只有之前的所有數字都被抵消了，major才會被修改

major

=nums[i

+1]else

:count+=1

i+=1if

count==0

:# 表示所有數字都被抵消了

return-1

return

major

5樓：bazhahei

首先眾數是個數大於一半的數，所以肯定最多只有乙個;

其次，從第一選手開始闖關(沒有回頭路)，遇到「非我同類」就「同歸於盡」，相反遇到「同類」就相伴而行，若最後我方拼得「彈盡糧絕」，就換這條路上的下一位選手從第一位選手倒下的節點繼續闖關，值得注意的是，其實這位選手的「同類」在第一位選手(及「同類」)闖關的途中，也同時消耗了兵力，參與了戰鬥，所以從這個節點開始，重複之前的操作，繼續拼殺，以此類推。若終點至少還有一人沒有倒下，那這位選手必定為「天選之子」(總數)~

6樓：

為什麼答案能寫那麼長呢。。。

核心就是對拼消耗。

玩乙個諸侯爭霸的遊戲，假設你方人口超過總人口一半以上，並且能保證每個人口出去幹仗都能一對一同歸於盡。最後還有人活下來的國家就是勝利。

那就大混戰唄，最差所有人都聯合起來對付你（對應你每次選擇作為計數器的數都是眾數），或者其他國家也會相互攻擊（會選擇其他數作為計數器的數），但是只要你們不要內鬥，最後肯定你贏。

最後能剩下的必定是自己人。

7樓：也獨有一種大意

169. Majority Element · Issue #122 · qbit-s/LeetCode

今天刷題刷到了，我使用迴圈不變數證明了下，證明了4個性質，能證明摩爾投票

8樓：這波很強勢

其實我覺得這個問題，用歸納法來理解，會更好一些。

根據題意，首先呢，如果乙個陣列存在超過n/2的眾數，那麼n/2+x個眾數， n/2-x個其他數（x>=1)。

9樓：

哈哈，題主怕不是在刷LeetCode吧。我是刷到求眾數這一題，不會做，上網搜尋題解，知道的這一演算法。一開始也不是很懂，後來看了 @喝七喜的回答，大概懂了，他講的非常好。不過沒有證明

首先，可以證明最終不會乙個數字都不剩。

原因：假設兩兩抵消之後，最終乙個數字都不剩。那麼就是說一共有偶數個數字，假設有n個，那麼n = 2k，k是整數。

所以是進行了k次兩兩抵消。又因為一定存在眾數 (數量超過n/2 = k的數字 )，所以該眾數出現次數至少為k+1。由抽屜原理，這就會導致前面兩兩抵消的某一對數字是一樣的。

這是矛盾的。所以這就證明了最終不會乙個數字都不剩，至少剩下乙個。

假設最終剩下的那一種數字是a，假設前面進行了k次兩兩抵消。要證明a是欲求的眾數，即證明其他數字不可能是眾數。由於抽屜原理，在前面抵消的數字中，同一種數字最多出現k次，即是除了a之外的數字最多出現k次。

而且最終至少剩下乙個數字，所以數字的總數量大於等於2k+1。那麼除了a之外的數字出現的頻率<= k/(2k+1) < k/2k = 1/2，所以證明了除了a之外的數字均不會是眾數。那麼就是說最終剩下的那種數字a是所求眾數。

LeetCode 每日一題 169. 求眾數

10樓：

這裡有題目可以幫助你理解。

Majority Element

n/2 times.

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

class

Solution

;else

(num

==res)?

++cnt:--

cnt;}}};

如何理解摩爾投票演算法？

如何理解Kosaraju演算法？

如何理解 Johnson Trotter 演算法來生成全排列？

如何理解MOEAD 演算法？

其他用戶還看了：