Leetcode Note: Go - Remove Element
Remove Element - LeetCode
https://leetcode.com/problems/remove-element/
- Go 言語で取り組んだメモ
所感
- シンプルにやるなら for ループ回しつつ
nums[i]とvalが一致するか判定すれば良い - しかし問題文のジャッジ内容がひねってあるので、その点注意
kとしては length を return- for loop の中での assert が成功するように
numsを操作する必要がある
実装準備
func assert(a interface{}, b interface{}) bool {
if a == b {
return true
}
return false
}
func removeElement(nums []int, val int) int {
return 0
}
func main() {
// nums := []int{3,2,2,3}
// val := 3
// expectedNums := []int{2, 2}
nums := []int{0,1,2,2,3,0,4,2}
val := 2
expectedNums := []int{0,1,4,0,3}
k := removeElement(nums, val)
fmt.Println(k, len(expectedNums))
fmt.Println(assert(k, len(expectedNums)))
fmt.Println(nums)
fmt.Println(expectedNums)
}v1
func assert(a interface{}, b interface{}) bool {
if a == b {
return true
}
return false
}
func removeElement(nums []int, val int) int {
count := 0
for i := 0; i < len(nums); i++ {
if nums[i] != val {
count++
} else {
nums = append(nums[:i], nums[i+1:])
}
}
return count
}
func main() {
// nums := []int{3,2,2,3}
// val := 3
// expectedNums := []int{2, 2}
nums := []int{0,1,2,2,3,0,4,2}
val := 2
expectedNums := []int{0,1,4,0,3}
k := removeElement(nums, val)
fmt.Println(k, len(expectedNums))
fmt.Println(assert(k, len(expectedNums)))
fmt.Println(nums)
fmt.Println(expectedNums)
// fmt.Println("====== for loop =====")
// for i := 0; i < len(expectedNums); i++ {
// fmt.Println(nums[i], expectedNums[i])
// fmt.Println(assert(nums[i], expectedNums[i]))
// }
}nums[i] != valの場合にnums[i]を削除するという実装がうまくできない・・・- そもそも LeetCode のエディタで Run Code した結果と異なるので、動作環境として不完全だった
- どこか悪いのか分からず・・・
- わからんので Solution 見てみる
v2
func removeElement(nums []int, val int) int {
i := 0
for j := 0; j < len(nums); j++ {
if nums[j] != val {
nums[i] = nums[j]
i++
}
}
return i
}- Solution の Approach 1: Two Pointers で実装してみたが、うまく動かず
- これちゃんと動いてた
- なぜ動いてないかと思ってしまったかと言うと、
num = [0,1,2,2,3,0,4,2], val = 2という input で Run Code した output が[0,1,3,0,4]で expected が[0,1,4,0,3]だったので、順序が違うと思ってしまった - 問題としては要素の数値が正当であれば順序は問わない仕様だったので、結果として問題なかった。問題文を読めていない。
回答
func removeElement(nums []int, val int) int {
i := 0
n := len(nums)
for i < n {
if nums[i] == val {
nums[i] = nums[n - 1]
n--
} else {
i++
}
}
return n
}- Solution の Approach 2: Two Pointers - when elements to remove are rare を見て実装したらうまく動いた
- 2つ のポインタを用意
i: 初期値は 0nums[i] != valならi++
n: 初期値は num の lengthnums[i] == valならnums[i] = nums[n - 1]- num の長さを詰める
- current element と last element の swap
n--:- 長さを詰めるのでデクリメント
- in-place で配列 nums を操作するというのが難しい
- 配列のコピーを作成せずに、配列から要素を削除する・・・というアプローチをひらめいて実装する力が必要
- ただ golang の場合
nums[i] = nums[n - 1]するだけだと delete element できてない気がするが LeetCode 側の呼び出しで削除されているという感じなんだろうか
https://go.dev/play/p/jDJz2p1K_mn
package main
import "fmt"
func removeElement(nums []int, val int) int {
i := 0
n := len(nums)
for i < n {
if nums[i] == val {
nums[i] = nums[n-1]
n--
} else {
i++
}
}
return n
}
func main() {
nums := []int{1, 2, 3, 4, 5}
val := 2
fmt.Println(nums) // [1 2 3 4 5]
removeElement(nums, val)
fmt.Println(nums) // [1 5 3 4 5] になってしまうので Delete Element できてない
}- Go らしく実装するのであれば append や copy を使って Slice から特定要素を削除するような実装になりそう
Go 言語でスライスから要素を消すには
https://zenn.dev/mattn/articles/31dfed3c89956d
- 改めて Custom Judge のコードを読んだら理解できた
- assert で判定する際には removeElement から return された数値を長さから引いた数のループを行うので、配列の長さそのものを変更するのではなくて、配列の先頭からカウントして valid な数値が格納されてれば OK だった
- 例えば
nums = [0,1,2,2,3,0,4,2], val = 2という input なら - nums の中で val と一致する要素数は 3 なので removeElement は 3 を return する
- nums の length は 8 で、 removeElement return の 3 を引いて 5
- よって assert 判定を行うループは 0 - 4 の範囲で行う
- そのため
nums = [0,1,4,0,3,2,2,2]というデータに置き換わっていれば OK - 2 の部分は便宜上 2 になっているが、仕様上なんでも OK ということ
- 問題文だと
_が入っているので静的型付け言語で表現できないじゃん・・・とか思ってた。問題文を読めていない〜
- 問題文だと
- 例えば