問題描述

給定一個大小為 n 的數組，找出其中所有出現超過 ⌊ n/2 ⌋ 次的元素。

解法一

解題思路:

• 使用摩爾投票法（Boyer-Moore Voting Algorithm）來找出可能的候選多數元素。
• 遍歷數組，使用兩個變量candidate和count，candidate存儲當前候選的多數元素，count用於記錄當前候選元素的票數。
• 如果count為0，則candidate更新為當前遍歷到的元素。
• 如果count不為0，且當前元素與candidate相同，則count加1；如果不同，則count減1。
• 遍歷結束後，candidate即為可能的多數元素。
• 再次遍歷數組，統計candidate出現的次數，如果大於n/2，則為所求的多數元素。

/*
 * @lc app=leetcode.cn id=169 lang=javascript
 *
 * [169] 多數元素
 */

// @lc code=start
function majorityElement(nums) {
    let candidate = null, count = 0;
    for (let num of nums) {
        if (count === 0) {
            candidate = num;
        }
        if (num === candidate) {
            count++;
        } else {
            count--;
        }
    }
    let result = [];
    count = 0;
    for (let num of nums) {
        if (num === candidate) {
            count++;
        }
    }
    if (count > nums.length / 2) {
        result.push(candidate);
    }
    return result;
}
// @lc code=end