1、題目描述
給定一個(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
說(shuō)明:
此題也叫做尋找多數(shù)元素/主元素問(wèn)題。解決這個(gè)問(wèn)題有好多種方法，蠻力方法就是把序列中的每個(gè)元素和其他每個(gè)元素比較，并且對(duì)每個(gè)元素計(jì)數(shù)，如果某個(gè)元素的計(jì)數(shù)大于n/2，就可以判斷它是多數(shù)元素，否則無(wú)多數(shù)元素。但是這樣的比較次數(shù)是n(n-1)/2=O(n^2)，復(fù)雜度高。比較有效的算法是先對(duì)這些元素排序，并且計(jì)算每個(gè)元素在序列中出現(xiàn)的次數(shù)，最壞情況下是O(nlogn)。因?yàn)榕判蜻@一步需要O(nlogn)次比較，也相對(duì)比較高，是不符合時(shí)間上的要求的，因此就有了一種相比之下更聰明的方法。
2、解法：
在原序列中去除兩個(gè)不同的元素以后，原序列中的多數(shù)元素在新的序列中還是多數(shù)元素
說(shuō)明
采用count來(lái)標(biāo)記主元素的個(gè)數(shù)，假設(shè)第一個(gè)是主元素，從第二個(gè)開(kāi)始比對(duì)，如果相等，則count++，否則，則是count--,當(dāng)count減到0的時(shí)候，主元素默認(rèn)為下一個(gè)。count加減的過(guò)程中，就是在模擬去掉兩個(gè)不同元素的過(guò)程！
代碼如下:
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;
}
經(jīng)測(cè)試，可行！
