[leetcode 39/169]PHP計算配列に現れる回数が半分を超える数字

原文リンク:のブログ
PHP計算配列の出現回数が半分を超える数字
配列の1つの数字が配列の長さの半分を超える回数がある場合は、この数字を見つけてください.配列は空ではなく、与えられた配列には常に多くの要素が存在すると仮定できます.
例1:入力:[1,2,3,2,2,2,5,4,2]出力:2
ソース:LeetCodeリンク:https://leetcode-cn.com/probl...
問題を解く考え方1array_count_values関数のような機能です
コード#コード#

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        $halfLength = floor(count($nums) / 2);
        $check = [];
        foreach ($nums as $item) {
            if ($check[$item] > $halfLength) {
                return $item;
            }

            $check[$item] += 1;
        }
    }
}

解題構想2-モル投票法
ムーア投票アルゴリズム(Boyer–Moore majority vote algorithm)は、O(n)の時間的複雑さとO(1)の空間的複雑さの下で線形テーブルに半分以上の要素が現れるアルゴリズムを探し、ストリームの思想を用いてデータを処理する.
場面:どのようにして任意の候補者(票が無秩序)で、得票数が圧倒的に優れている人を選出しますか?(この人の得票は他のすべての人の和を上回って、つまり1/2以上を占めています).
票が整列している場合、この問題は非常に簡単です.線形テーブル全体の中位数は必ず長さが1/2を超えるセグメントにあるからです.セグメントが先頭にある場合、セグメントの末尾は必ず1/2を超え、セグメントが末尾にある場合、セグメントの先頭は必ず1/2未満です.線形テーブルの中位数を調べるだけで結果が得られ,時間的複雑度はO(1)であった.
票が無秩序である場合,この方法を採用するには線形テーブルをソートする必要があり,時間的複雑さはソートアルゴリズムを採用する時間的複雑さに増大する.
では、線形テーブルを順番にアクセスするだけで答えを得る方法はありますか?それがモル投票法です.
原理:モルアルゴリズムの核心思想は任意の要素の2つの相殺で、最後に残った要素は必ず出現回数が1/2を超えて、アルゴリズムは1つのシーケンス要素numと1つのカウンタを維持して、numは現在の数字を示して、カウンタはこの要素がまたいくつかの要素を相殺することができることを示します.
コード#コード#

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function majorityElement($nums) {
        $votes = 0;
        foreach ($nums as $num) {
            if($votes == 0) $x = $num;
            $votes += $num == $x ? 1 : -1;
        }

        return $x;
    }
}

リファレンスリンク

モル投票アルゴリズム(二重角度理解)

leetcode公式問題解

推薦個アルゴリズム面接通関40講割引購入