27. Remove Element

問題URL

https://leetcode.com/problems/remove-element/description/

解法1

シンプルにslices packageを使って解いた。

func removeElement(nums []int, val int) int {
    nums = slices.DeleteFunc(nums, func(n int) bool {
        return n == val
    })

    return len(nums)
}

標準ライブラリに任せただけ。これで終わりだとつまらないので、ライブラリの実装を見てみる。

func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
    //  del関数を満たす最初の要素のindexを返す。満たす要素が無ければ、-1
    // i は削除対象の最初の要素のindex
    i := IndexFunc(s, del)
    if i == -1 {
        return s
    }
    // Don't start copying elements until we find one to delete.
    // 削除対象の要素の次indexからループスタート
    // 削除対象外の要素がs[0:i] 間に来るように値を詰め替える
    for j := i + 1; j < len(s); j++ {
     
        if v := s[j]; !del(v) {
            s[i] = v
            i++
        }
    }
    clear(s[i:]) // zero/nil out the obsolete elements, for GC
    return s[:i] // 削除対象外の要素部分のみを返す
}

slices package DeleteFuncのソースコード

解法2

1. 削除対象外の要素のスライスを作る
2. copy で nums を上書く

func removeElement(nums []int, val int) int {
    filtered := make([]int, 0, len(nums))
    for _, v := range nums {
        if v != val {
            filtered = append(filtered, v)
        }
    }

    copy(nums, filtered)
    return len(filtered)
}

解法3

問題文には下記のように書いてある。

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.

• 削除対象外の要素が先頭に並んでいること
• 削除対象外の要素数を返すこと

上記2点さえ満たせば良いので、シンプルに次のようにするだけでOK。

func removeElement(nums []int, val int) int {
    k := 0
    for _, v := range nums {
        if v != val {
            nums[k] = v
            k++
        }
    }
    return k
}

感想

解法3は思いつかず、Solutionsで見つけた解法。 たったこれだけで済む問題だとは気づかなかった。まだまだ頭が硬い。

ただ、ぱっと解法3を思いつくよりも、 DeleteFunc の実装をササッと自前で書けるようになりたい。 slices packageのコードを見る良い機会になった。

（実務だと解法1で十分だからね... 😅）