LeetCode 905. Sort Array By Parity
はじめに
LeetCode 「905. Sort Array By Parity」の問題をGoで解きました。
問題
問題文
Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.
和訳
整数配列 nums が与えられたとき、すべての偶数整数を配列の先頭に移動させ、その後にすべての奇数整数を移動させる。
この条件を満たす配列を返す。
補足：例にあるように偶数・奇数のそれぞれについては順序は問いません。
例
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Input: nums = [0]
Output: [0]
制約
- 1 <= nums.length <= 5000
- 0 <= nums[i] <= 5000
解答1
まず、シンプルな解答を考えました。
偶数用・奇数用のスライスを用意し、numsをループで回して偶数であれば偶数のスライスに追加・奇数であれば奇数のスライスに追加する方法です。
最後に偶数のスライス・奇数のスライスを結合して返します。
コード
func sortArrayByParity(nums []int) []int {
evens := []int{}
odds := []int{}
for _, num := range nums {
if num%2 == 0 {
evens = append(evens, num)
} else {
odds = append(odds, num)
}
}
return append(evens, odds...)
}
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(n)
解答2（Two Pointers パターン）
上記のパターンでは、偶数用・奇数用のスライスを新たに追加したので、追加分のメモリが必要になります。
追加分のメモリを使用しないより良い方法として、Two Pointersパターンがありますので解説します。
Two Pointers パターン
Two Pointers は、2つの異なる位置からポインタを動かしながら探索を行う方法です。
主に配列や文字列操作を効率化するために使われ、時間計算量をO(n)に抑えることができるのがメリットです。
今回は、配列の左端と右端から中央に向かってポインタを動かすというパターンで実装できます。
コード
func sortArrayByParity(nums []int) []int {
left, right := 0, len(nums)-1
for left < right {
// 偶数が見つかるまでleftを進める
for left < right && nums[left]%2 == 0 {
left++
}
// 奇数が見つかるまでrightを進める
for left < right && nums[right]%2 == 1 {
right--
}
if left < right {
// 偶数と奇数を入れ替える
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
return nums
}
leftは左から偶数を探すためのポインタ、rightは右から奇数を探すためのポインタです。
left < right の条件で偶数・奇数を見つけるまでポインタを進めて見つかったら入れ替えるということを繰り返します。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
Discussion