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，回传阵列中主要的元素是哪一个

参考资料