Time：2019/4/5
Title: Majority Element 2
Difficulty: medium
Author: 小鹿
問題：Majority Element 2
Given an integer array of size n, find all elements that appear more than ? n/3 ? times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
solve:
▉ 算法思路：
1畜普、上一篇是一個(gè)求超過 n/2 個(gè)數(shù)的數(shù)，采取的是用一個(gè)計(jì)數(shù)變量和計(jì)數(shù)元素變量來完成的群叶。本篇題目是超過 n/3 的個(gè)數(shù)吃挑， 我們分別用兩個(gè)變量來完成，條件限制是時(shí)間復(fù)雜度是O(n),空間復(fù)雜度為O(1)街立。
2舶衬、繼續(xù)使用摩投票算法，假設(shè)要投票赎离，選取票數(shù)超過 n/3 以上選為候選人逛犹，一個(gè) n 被分為三等份，也就是說最多有兩位當(dāng)選人。
3虽画、假設(shè)第一個(gè)人投甲舞蔽，第二個(gè)投乙，甲码撰、乙都站到臺(tái)上各個(gè)計(jì)數(shù)為 1 渗柿，隨之第三個(gè)投甲，第四個(gè)投乙脖岛，計(jì)數(shù)分別加 1 朵栖，第五個(gè)投丙，因?yàn)橹挥袃蓚€(gè)臺(tái)子柴梆，所以那就讓甲乙票數(shù)計(jì)數(shù)各減 1 陨溅，當(dāng)甲、乙的票數(shù)分別減到 0 之后轩性，第 m 個(gè)人投丙声登，就讓丙代替甲或已狠鸳，繼續(xù)遍歷數(shù)據(jù)揣苏，直到遍歷完成為止。
4件舵、上述只選擇出了那些有可能滿足條件的數(shù)據(jù)卸察，下面對(duì)cm、cn存儲(chǔ)的數(shù)據(jù)做驗(yàn)證铅祸。
▉ 其他解法：
如果沒有題目中時(shí)間復(fù)雜度和空間復(fù)雜度的限制坑质，有多種解決方法：
1、散列表解決：先遍歷一遍數(shù)據(jù)临梗，統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)涡扼，然后再遍歷一遍散列表，找出滿足條件的數(shù)字盟庞。時(shí)間復(fù)雜度為O(n)吃沪，空間復(fù)雜度為 O(n)。
2什猖、排序解決：先進(jìn)行一次排序（快排）票彪，然后遍歷數(shù)據(jù)，找出滿足條件的數(shù)據(jù)不狮。時(shí)間復(fù)雜度為O(nlogn)降铸，空間復(fù)雜度為O(1)。
▉ 代碼實(shí)現(xiàn)：
/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function(nums) {
let [m,n,cm,cn,countm,countn] = [0,0,0,0,0,0];
let result = [];
for(let i = 0;i < nums.length; ++i){
//m === nums[i]和n === nums[i]的判斷一定放到 cm === 0 和 cn === 0 之前摇零，負(fù)責(zé)產(chǎn)生 bug推掸。
if(m === nums[i]){
cm ++;
}else if(n === nums[i]){
cn ++;
}else if(cm === 0){
m = nums[i];
cm ++;
}else if(cn === 0){
n = nums[i];
cn ++;
}else{
cn--;
cm--;
}
}
//驗(yàn)證 cm、cn 存儲(chǔ)的數(shù)據(jù)
for(let index in nums){
if(nums[index] === m){
++countm;
}
if(nums[index] === n){
++countn;
}
}
if(countm > Math.floor(nums.length/3)){
result.push(m);
}
if(countn > Math.floor(nums.length/3) && n != m){
result.push(n);
}
return result;
};
//測試
let arr =[1,2,2,3,2,1,1,3];
console.log(majorityElement(arr));
歡迎關(guān)注我個(gè)人公眾號(hào)：「一個(gè)不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事谅畅。
LeetCode 其他題目解析俊嗽，請(qǐng)關(guān)注我Github：https://github.com/luxiangqiang/JS-LeetCode
