𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁

LeetCode 169は、配列内のマジョリティ要素（多数派要素）を見つける問題です。マジョリティ要素は $n / 2$ 回より多く出現します。また、その要素は常に存在するものと仮定します。

これには2つの解法があります。

アプローチ 1: Map を使用する方法

この方法は、Map を使用して各数値の出現回数をカウントします。

• カウントを保存するための Map を作成します。
• 配列をループします。
• 各数値のカウントを更新します。
• Map をループして、カウントが $n / 2$ を超える数値を見つけます。

計算量:

• 時間: $O(n)$（2つの連続するループを使用するため）。
• 空間: $O(n)$（ユニークな要素の数に応じて Map が大きくなるため）。

アプローチ 2: Boyer-Moore Voting Algorithm

これは、定数メモリを使用して問題を解決する最適化された方法です。

数値を対立するチームと考えてみてください。ある数値が異なる数値に出会うたびに、それらは互いに打ち消し合います。マジョリティ要素は全体の半分以上を占めるため、最終的に生き残るのは必ずその要素になります。

仕組み:

• 候補（candidate）を選び、カウントを 0 に設定します。
• 配列をループします。
• カウントが 0 の場合、現在の数値を候補に設定します。
• 現在の数値が候補と一致する場合、カウントを 1 増やします。
• 一致しない場合は、カウントを 1 減らします。

計算量:

• 時間: $O(n)$（配列を1回スキャンするだけのため）。
• 空間: $O(1)$（2つの変数のみを使用するため）。

なぜ重要なのか:

どちらの方法も時間計算量は $O(n)$ です。しかし、2番目のアプローチはメモリの使用量が大幅に少なくなります。Map を必要としないため、大規模なデータセットに対してより適しています。

Source: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6