多数派要素

説明

袋の中のキャンディのうち、過半数を占めている色があるかどうかを見分けるのが、今回の任務です。🍬 過半数を占める要素とは、コレクションの中で半分を超える割合を占める要素のことです。色を表す要素のリストが与えられたら、過半数を占める色があればその色を返し、そうでなければ過半数が見つからなかったことを示してください。

単純なリスト[Red, Red, Blue, Red, Green]の場合、返す値はRedです。5つの要素のうち、Redが3回現れているからです。しかし、リスト[Red, Red, Blue, Green]の場合、Redが最も多く現れる色ではあっても、過半数はありません。2/4は要素の半分より大きくはないからです。

実装

• ボーナスポイント：どんな型のリストでも多数派の要素を見つけられるように、実装を一般化できますか？
• ボーナスポイント：多数派を見つけるときに選べる要素がたくさんある場合でも、実装は十分な性能を発揮しますか？
• majorityFinder関数は好きな方法で実装できますが、MyStore abilityを使ういくつかのスタブを用意してあります。（MyStore abilityは標準ライブラリのStoreと同じものですが、曖昧さを避けるためにここでは少し違う名前を付けています。）このabilityを使う場合、runWithハンドラーを実装する必要があります。runWithは、MyStore abilityを使う関数を実行した結果と、MyStoreの最終的な状態の両方を返します。
• abilityハンドラーがどのように状態を追跡できるかについては、abilityハンドラーのドキュメントで詳しく読むことができます。

---

出典

Boyer Moore Majority Vote Algorithm