多數(shù)元素

題目描述：給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例說明請(qǐng)見LeetCode官網(wǎng)。

來源：力扣（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)注明出處。

解法一：HashMap

利用java的HashMap，key存不同的數(shù)字，value存對(duì)應(yīng)的數(shù)字出現(xiàn)的次數(shù)：

• 遍歷nums，將每個(gè)數(shù)字放入HashMap里；

• 比較得到的HashMap，比較每個(gè)數(shù)字出現(xiàn)的次數(shù)，得到出現(xiàn)次數(shù)最多的數(shù)字，返回結(jié)果。

解法二：摩爾投票算法

摩爾投票算法就是把相異的2個(gè)數(shù)都消耗掉，由于總是存在多數(shù)元素，意味著相異的數(shù)消耗掉之后只可能留下那個(gè)多數(shù)元素。具體過程如下，用result記錄最終的那個(gè)多數(shù)，初始化為數(shù)組的第一個(gè)元素，count記錄這個(gè)數(shù)字重復(fù)的次數(shù)：

• 首先，如果count為0，表示前面的相異的數(shù)字都消耗完了，result賦值為當(dāng)前的數(shù)，count為1；

• 如果count大于0：

• 如果result和當(dāng)前元素相等，則count加1；

• 如果result和當(dāng)前元素不相等，則count減一，即消耗掉一對(duì)相異的數(shù)。

最終result一定是那個(gè)多數(shù)元素。

【每日寄語】 所有逆襲，都是有備而來；所有光芒，都是努力埋下的伏筆。