題目

169. 求眾數

給定一個大小為 n 的數組，找到其中的眾數。眾數是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，並且給定的數組總是存在眾數。

示例 1:

輸入: [3,2,3]
輸出: 3

示例 2:

輸入: [2,2,1,1,1,2,2]
輸出: 2

眾數（Mode）是統計學名詞，在統計分佈上具有明顯集中趨勢點的數值，代表數據的一般水平（眾數可以不存在或多於一個）。 修正定義：是一組數據中出現次數最多的數值，叫眾數，有時眾數在一組數中有好幾個。用 M 表示。 理性理解：簡單的說，就是一組數據中占比例最多的那個數。--《百度百科》

解答

解答一、對象中存儲所有元素及出現次數

拿到題目，我的第一想法就是for迴圈，

使用for迴圈遍歷元素並記下每個元素出現的次數，

存儲在一個對象中。

代碼如下：（leetcode已提交通過，執行用時：128ms）

/**
*未考慮nums數組元素個數為偶數的情況
*未考慮存在多個眾數的情況
*未考慮不存在眾數的情況
*未考慮數組中存在非數字的情況
*/

var majorityElement = function(nums) {
    var obj={};                         
    var halfNum=nums.length/2;
    var mode;
    if (nums.length===1) return nums[0];
    for (let i=0;i<nums.length;i++){    //拆解數組中元素，賦值為對象的key
       if(obj[nums[i]]){                //遍歷，若已有該key，
           obj[nums[i]]+=1;             //對應的value+1
           if(obj[nums[i]]>halfNum){    //若該key對應的value大於數組元素個數的半數
                mode=nums[i];
                return mode;            //返回該key值
           }
       }else{
           obj[nums[i]]=1;              //若沒有，加key，對應value賦值為1
       }
    }
};

解答二、假設法

for of 遍歷，假設第一個數為眾數，count計1，
其後的數字若相同則count 加1，否則count減1，
當count減為0時，假設此時新的num為眾數，繼續判斷，
眾數出現次數始終大於或等於所有元素個數的一半，
如果存在眾數，最終一定存在一個num，使得count大於0，
！！缺點：若不存在眾數，則會返回最後一個元素。

代碼如下：（leetcode已提交通過，執行用時：104ms）

let majorityElement = function(nums) {
    let count = 0;
    let mode = 0;
    for (let num of nums) {          
        if (count === 0) {            
            mode = num;               
        }                            
        count = mode === num ? count + 1 : count - 1;
    }                                 
    return mode;                     
};