更新於 2024/10/15閱讀時間約 3 分鐘

[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;
};


相關連結




分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.