CodilityのLesson2をGoで解いてみた
概要
オンラインコーディングの試験であるCodilityのLesson2を自分なりに解いてみました。 https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/
問題の要約
以下の条件で配列が生成される
- 要素: N個
- 空ではない
- 値は必ず奇数
- 同じ値はペアとして扱う
func Solution(A []int) int
は 配列を取得するとペアではない値を返します
アルゴリズムを組み立てる際の情報
- Nの範囲は[1..1,000,000]
- 値の範囲は[1..1,000,000,000]
- 一つを除く全ての値が偶数回発生する(ペアになる)
Sample Data
[9,3,9,3,9,7,9]
コード
package main import ( "fmt" "os" ) func main() { // 問題文の仮定リスト intList := []int{9, 3, 9, 3, 9, 7, 9} fmt.Println(`Solo Number:`, Solution(intList)) } // Solution はN個の要素数と奇数値のみで構成されたInt型の配列を受け取る // 値の中でペアになっていない値を返却する func Solution(A []int) int { // 配列が空の場合終了 if len(A) == 0 { fmt.Println("Not Include Items in Array") os.Exit(1) } // 重複判別用のmapを作成 mapForDecidePear := make(map[int]int) // 重複した分の数をValueにsetしていく // 要素が偶数の場合異常な値として処理 for _, val := range A { if val%2 == 0 { fmt.Println("Include Even Number in Array") os.Exit(1) break } mapForDecidePear[val] = mapForDecidePear[val] + 1 } // 重複していない要素はValueが1なのでそれを取り出す // 重複していない要素は一つしかないので見つかり次第抜けだす var soloValue = 0 for key, val := range mapForDecidePear { if val == 1 { soloValue = key break } } return soloValue }
結果 Solo Number: 7
解説
重複していない要素を判別する方法として,以下の方法も考えられました
ただ、今回こちらの方法を取ったのは以下の理由になります。
- 配列を回す回数は変わらないが、sortの中で匿名関数を使う必要があるため、複雑になってしまうこと
- 構造体を定義する必要がないこと
結論n+1問題を回避すればいいと思うので、特段問題ないと思います。