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

參考資料