[TS LeetCode] 169. Majority Element .Boyer-Moore 摩爾投票演算法

題目摘要

給定一個長度為n的整數陣列nums，請找出其中的「主要元素」。

主要元素指的是在陣列中出現次數超過⌊n / 2⌋的元素，我們可以假設主要元素一定存在於這個陣列中。

題目知識點

1. 主要元素：指的是在陣列中出現次數超過一半以上的元素。
2. 摩爾投票算法：一種有效的解決主要元素問題的方法，能夠在O(n)時間內找到主要元素。

先備知識

1. 了解陣列（Array）的基本概念和操作。
2. 熟悉JavaScript/TypeScript中的迴圈和條件判斷。
3. 理解如何使用變數來追蹤元素出現次數。

Boyer–Moore majority vote algorithm 多數投票演算法

是一種用於找出具有多數元素的算法，它在陣列中的應用情境以及使用限制如下

使用情境

1. 主要元素檢測： 多數投票演算法主要用於找出陣列中出現次數超過一半的主要元素。這在選舉或投票系統中非常有用，用於確定最多選票的候選人。
2. 數據流中的眾數：當你需要在數據流中即時找到最多出現的元素，摩爾投票算法可以動態處理數據並找出眾數。

使用限制

1. 主要元素必須存在：摩爾投票演算法假設主要元素一定存在於陣列中。如果主要元素可能不存在，則需要額外的檢查。
2. 不適用於多元素問題：這個算法僅適用於找出單一主要元素，當有多個主要元素時，它無法處理。
3. 具體數量未知：這個算法不適用於在事先不知道主要元素應該出現多少次的情況。它僅告訴你主要元素是否存在並找到它。

應用情境

在網頁頁面開發中，這種主要元素的問題常常應用在以下情境：

• 用戶投票：當需要確定在一次投票中哪個選項獲得了多數選票，可以使用主要元素算法。
• 購物網站庫存：在網上購物平台上，需要找到最暢銷的產品，以便進一步推廣，這可以使用主要元素概念。
• 活動參與者：在線上活動報名中，需要確定參與者中是否有某個主要參與者，以作出相關安排。

結論

這道題目中使用了摩爾投票算法，該算法可以高效地找出主要元素。這對於處理大型數據集中的主要元素問題非常有用，並且可以在O(n)時間內解決。摩爾投票算法的關鍵是使用兩個變數來追蹤候選元素和其出現次數，通過適當的條件判斷和更新，最終找到主要元素。這個方法在多個應用情境中都能派上用場，特別是當我們需要找到一組數據中的主要趨勢或最多的元素時。

解答:

Time Complexity : O(n)

n是陣列nums的長度

Space Complexity:O(1)

空間複雜度是指在執行程式期間所需的額外記憶體空間。這段程式碼中只使用了兩個變數，即"majority"和"count"，它們的空間消耗是固定的，與輸入陣列的大小無關。因此，空間複雜度是O(1)，稱為常數空間複雜度。

function majorityElement(nums: number[]): number {
    let majority: number = nums[0];
    let count: number = 0;

    for (let i = 0; i < nums.length; i++) {
        if (count === 0) {
            majority = nums[i];
        }

        majority === nums[i] ? count++ : count--
    }

    return majority;
};

相關連結