169. Majority Element

Leetcode 问题: 169. Majority Element
Categories:
Tags:

题目

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

传入一个整数阵列 nums 大小是 n，回传阵列中主要的元素是哪一个

主要的元素表示这个元素出现的次数超过 n/2 超过所有元素一半以上

Example

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

演算法 1，使用元素出现次数 Map

1. 纪录每个数字出现数量，并比较出现次数

如果目前元素数量大于最多的元素数量，则将目前主要元素设定为 目前主要元素

将最多的元素数量设定为目前元素数量

演算法 1，答案

JavaScript

function majorityElement(numsList) {
    var elementCountMap = {};
    var currentMajorityElement = 0;
    var maxCount = 0;
    for (var i = 0; i < numsList.length; i++) {
        // 目前数字
        var currentNumber = numsList[i];
        if (!elementCountMap[currentNumber]) {
            // 如果没有此数字 Map，设定预设值
            elementCountMap[currentNumber] = 0;
        }
        // 目前数字数量 ++
        elementCountMap[currentNumber]++;
        if (elementCountMap[currentNumber] > maxCount) {
            // 如果目前元素数量大于最多的元素数量
            currentMajorityElement = currentNumber;
            // 设定目前最多元素数量为当前元素数量
            maxCount = elementCountMap[currentNumber];
        }
    }
    return currentMajorityElement;
}

TypeScript

function majorityElement(numsList: number[]): number {
    let elementCountMap: any = {};
    let currentMajorityElement = 0;
    let maxCount = 0;

    for (let i = 0; i < numsList.length; i++) {
        // 目前数字
        let currentNumber = numsList[i];
        if (!elementCountMap[currentNumber]) {
            // 如果没有此数字 Map，设定预设值
            elementCountMap[currentNumber] = 0;
        }
        // 目前数字数量 ++
        elementCountMap[currentNumber]++;
        if (elementCountMap[currentNumber] > maxCount) {
            // 如果目前元素数量大于最多的元素数量
            currentMajorityElement = currentNumber;
            // 设定目前最多元素数量为当前元素数量
            maxCount = elementCountMap[currentNumber];
        }
    }

    return currentMajorityElement;
};

演算法 2，使用 Boyer-Moore 演算法

1. 纪录元素出现次数

当主要元素与目前元素相同时，元素数量 +1

当主要元素与目前元素不同时，元素数量 -1

2. 如果元素数量是 0，重新设定主要元素

如果元素数量为 0，表示前面的元素目前相互抵销，导致还没找到主要元素，或者有主要元素，但元素数量小于 1/2

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

因为如果多于 1/2，那元素数量不会被抵消扣除变成 0

前面的元素互相抵销，所以前面的元素无法当作主要元素的判断

使用后面的剩馀元素 n - i 去判断主要元素，后面的主要元素一定会大于 1/2

等整个元素都看过后，最后会找到主要园素

演算法 2，答案

JavaScript

function majorityElement(numsList) {
    var currentMajorityElement = numsList[0];
    var currentCount = 0;
    for (var i = 0; i < numsList.length; i++) {
        // 目前数字
        var currentNumber = numsList[i];
        if (currentCount == 0) {
            // 如果目前元素数量被扣到为 0，将目前数字设定为最主要元素
            currentMajorityElement = currentNumber;
        }
        if (currentMajorityElement == currentNumber) {
            // 如果「目前元素」与「主要元素」相同，元素数量 + 1
            currentCount++;
        }
        else {
            // 如果「目前元素」与「主要元素」不同，元素数量 - 1
            currentCount--;
        }
    }
    return currentMajorityElement;
}

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

参考资料