Boyer-Moore 博耶穆爾字串搜尋

Boyer-Moore 博耶穆爾字串搜尋
Categories:
Tags:

找尋出現在陣列中主要的元素是哪一個

假如陣列元素長度是 n，主要的元素表示這個元素出現的次數超過 n/2 超過所有元素一半以上

演算法

1. 紀錄元素出現次數

當主要元素與目前元素相同時，元素數量 +1

當主要元素與目前元素不同時，元素數量 -1

2. 如果元素數量是 0，重新設定主要元素

如果元素數量為 0，表示前面的元素目前相互抵銷，導致還沒找到主要元素，或者有主要元素，但元素數量小於 1/2

e.g. [1,1,1,2,2,2]

因為如果多於 1/2，那元素數量不會被抵消扣除變成 0

前面的元素互相抵銷，所以前面的元素無法當作主要元素的判斷

使用後面的剩餘元素 n - i 去判斷主要元素，後面的主要元素一定會大於 1/2

等整個元素都看過後，最後會找到主要園素

程式

TypeScript

function majorityElement(numsList: number[]): number {
    let currentMajorityElement = numsList[0];
    let currentCount = 0;

    for (let i = 0; i < numsList.length; i++) {
        // 目前數字
        let currentNumber = numsList[i];
        if (currentCount == 0) {
            // 如果目前元素數量被扣到為 0，將目前數字設定為最主要元素
            currentMajorityElement = currentNumber;
        }

        if (currentMajorityElement == currentNumber) {
            // 如果「目前元素」與「主要元素」相同，元素數量 + 1
            currentCount++;
        } else {
            // 如果「目前元素」與「主要元素」不同，元素數量 - 1
            currentCount--;
        }
    }

    return currentMajorityElement;
};

LeetCode

題目 說明
169. Majority Element 傳入一個整數陣列 nums 大小是 n，回傳陣列中主要的元素是哪一個

參考資料