給定一個(gè)大小為 n 的數(shù)組且轨，找到其中的多數(shù)元素毛肋。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素梨水。你可以假設(shè)數(shù)組是非空的老客，并且給定的數(shù)組總是存在多數(shù)元素僚饭。
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/majority-element
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)胧砰，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處鳍鸵。
來(lái)自lc的一道Easy題目，大概在一年前做過(guò)尉间，當(dāng)時(shí)的方法很樸素权纤，我把提交貼下面。
現(xiàn)在一看確實(shí)很青澀乌妒。不管在時(shí)間還是空間上都沒(méi)有多大優(yōu)勢(shì)汹想。主要想法是用hash表存數(shù)據(jù)，其實(shí)內(nèi)存上耗費(fèi)也不是很大撤蚊。
寫(xiě)這篇文章主要說(shuō)一下其他的思路古掏。分享幾個(gè)很好玩的想法。
1. 排序取中
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
至于這個(gè)方法侦啸，其實(shí)是一種比較簡(jiǎn)單且巧妙的方法槽唾，一年之前看到這個(gè)方法的時(shí)候就很驚艷，一年之后再看到這道題光涂，腦海里立馬復(fù)現(xiàn)的也是這個(gè)方法庞萍。
使用這個(gè)方法有一個(gè)前提條件，就是題目中所描述的 你可以假設(shè)數(shù)組是非空的忘闻，并且給定的數(shù)組總是存在多數(shù)元素钝计。，首先明確定義，多數(shù)是 占 n/2 以上的數(shù)私恬，并不是眾數(shù)债沮。 所以排序后，如果某個(gè)數(shù)數(shù)量多于一半本鸣，那么這個(gè)數(shù)一定在一半位置上有存在疫衩。那么這個(gè)也是這個(gè)算法的巧妙之處。
2. 摩爾投票法
這邊引用網(wǎng)上的例子來(lái)描述一下荣德。
核心就是對(duì)拼消耗闷煤。
玩一個(gè)諸侯爭(zhēng)霸的游戲，假設(shè)你方人口超過(guò)總?cè)丝谝话胍陨箱陶埃⑶夷鼙ＷC每個(gè)人口出去干仗都能一對(duì)一同歸于盡鲤拿。最后還有人活下來(lái)的國(guó)家就是勝利。
那就大混戰(zhàn)唄饲宛，最差所有人都聯(lián)合起來(lái)對(duì)付你（對(duì)應(yīng)你每次選擇作為計(jì)數(shù)器的數(shù)都是眾數(shù)），或者其他國(guó)家也會(huì)相互攻擊（會(huì)選擇其他數(shù)作為計(jì)數(shù)器的數(shù)）嗜价，但是只要你們不要內(nèi)斗艇抠，最后肯定你贏。
最后能剩下的必定是自己人久锥。
這里面的內(nèi)容就是對(duì)拼和消耗家淤。
如一個(gè)數(shù)組。A = [2,2,1,1,1,2,2]
我們可以假設(shè)我方是2瑟由，敵方是1絮重，那么2多，最后一定勝出歹苦。
那就從第一個(gè)A[0] = 2開(kāi)始青伤，遇到自己人就加一，遇到敵人就減一殴瘦，好比打仗狠角，碰到自己人，隊(duì)伍就壯大蚪腋，遇到敵人就互相kill丰歌。到A[3] = 1 的時(shí)候，2211正好相互抵消屉凯，本輪結(jié)束立帖，繼續(xù)后面的 此時(shí)1變主場(chǎng)，然后與2比拼悠砚，沒(méi)成想最后還有一個(gè)2晓勇，最終我方勝利。
在代碼中的體現(xiàn)如下。
public int majorityElement(int[] nums) {
int count = 1;
int maj = nums[0];
for (int i = 1; i < nums.length; i++) {
if (maj == nums[i])
count++;
else {
count--;
if (count == 0) {
maj = nums[i + 1];
}
}
}
return maj;
}
上面介紹了幾種思想宵蕉，后兩種比較巧妙酝静，可以詳細(xì)研究一下。
