Zenn
🦍

【LeetCode】169. Majority Element に挑戦！！

2024/12/17に公開
Go
アルゴリズム
LeetCode
初級
tech

問題

配列 nums がサイズ n で与えられたとき、過半数を占める要素 を返してください。

過半数を占める要素 とは、配列内で ⌊n / 2⌋ 回（n を 2 で割った商の切り捨て）を超えて現れる要素のことです。

例 1：
入力: nums = [3,2,3]
出力: 3

例 2：
入力: nums = [2,2,1,1,1,2,2]
出力: 2

制約

n == nums.length
1 <= n <= 5 * 10^4
-10^9 <= nums[i] <= 10^9

実験（取っ掛かり）

まず、プログラムではなく人間が問題を解く場合を考えてみましょう。

例 1：
入力: nums = [3,2,3]
出力: 3

例１の場合は、左から見ていき、3が1回、2が1回、また3が出たので2回とカウントしていきますね。そして3が最も多く出現しているので出力は3となります。（もしくは全体的にみて、3が2回で2が1回と瞬時にわかるかと思います。）
ここでポイントとなるのは、「3が2回、2が1回」という部分です。
何か思いつくことはありますでしょうか？
それでは、こちらはいかがでしょうか？「名前は太郎、年齢は27歳、出身国は日本」

{"name": "Taro", "age": 27, "country": "Japan"}

この形はキー・バリューの連想配列ですね。Go言語の場合だとmapになります。

mapの復習（Go言語）

Go では map 型の変数を次の形式で宣言します。

// map[キー]バリュー{}
m := map[string]string{}

宣言と同時に初期化

account := map[string]string{
	"name": "Taro",
	"country": "Japan",
}

fmt.Println("account[\"name\"] =", account["name"])
fmt.Println("account[\"country\"] =", account["country"])

◆ 出力結果（キーを指定することでバリューが表示される）
account["name"] = Taro
account["country"] = Japan

forで全て出力

for key, value := range account {
   fmt.Println("key =", key)
   fmt.Println("value =", value)
}

◆ 出力結果
key = country
value = Japan
key = name
value = Taro

少しだけ上記を応用することで対象となる配列のキーの出現回数をmap型でカウントすることができます。

解法（思考プロセス）

方針：
map型を使い、キーの出現回数を数える
{3:2回出現した, 2:1回出現した}
⇔ キーは数、バリューは回数

number_counts(map型)を準備し、nums = [3,2,3]を左から1つずつ見ていき、number_countsに「キーは数、バリューは回数（カウントアップさせる）」を格納していきます。

具体的には、
1. number_countsをmap[string]int{}で準備する。

2. numsを1つずつループする。

3. number_counts[num]で回数をカウントアップ
→ numsの最初は3なので、number_counts[3]++ （3は1回目）

4. number_counts[num]で回数をカウントアップ
→ 次は2なので、number_counts[2]++（2は1回目）

5. number_counts[num]で回数をカウントアップ
→ 次は3なので、number_counts[3]++（3は2回目）

解法（実装）

package main

import "fmt"

func main() {

	nums := []int{3, 2, 3}

	fmt.Println("majorityElement(nums):", majorityElement(nums))

}

// 最も出現回数が多い数を返す
func majorityElement(nums []int) int {

	// 出現回数をカウントするための mapを準備する
	number_counts_map := map[int]int{}

	// 対象の配列(nums)を一つずつ取り出して、出現回数をカウントする
	// 結果として、number_counts_mapに{出現した数:X回}という形で格納される
	for _, num := range nums {
		number_counts_map[num]++
	}

	var majorityNumber, majorityCount int

	// mapを一つずつ検索し、カウント回数(count)が多いものを随時最大値（majorityCount）として格納する
	for num, count := range number_counts_map {
		if count > majorityCount {
			majorityNumber = num
			majorityCount = count
		}
	}
	return majorityNumber
}

main.go 実行結果

majorityElement(nums): 3

例２ 実行結果

majorityElement(nums): 2

Discussion