はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

9問目（問題27)

27. Remove Element

• 問題内容(日本語訳)

配列numsと値valを指定して、その値のすべてのインスタンスをインプレースで削除し、新しい長さを返します。

別の配列に余分なスペースを割り当てないでください。O（1）の余分なメモリを使用して入力配列をインプレースで変更する必要があります。

要素の順序は変更できます。新しい長さを超えて何を残すかは問題ではありません。

明確化：

戻り値が整数であるのに、答えが配列である理由がわかりませんか？

入力配列は参照によって渡されることに注意してください。これは、入力配列への変更が呼び出し元にも認識されることを意味します。

内部的には、これについて考えることができます。

// numsは参照によって渡されます。（つまり、コピーを作成せずに）
int len = removeElement（nums、val）;

//関数内のnumsへの変更は、呼び出し元に認識されます。
//関数から返された長さを使用して、最初のlen要素を出力します。
for（int i = 0; i <len; i ++）{
    print（nums [i]）;
}

Example 1:

  Input: nums = [1,1,2]
  Output: 2, nums = [1,2]
  Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

  Input: nums = [0,0,1,1,1,2,2,3,3,4]
  Output: 5, nums = [0,1,2,3,4]
  Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

ヒント1

問題の説明では、配列をインプレースで変更するように明確に求められており、配列の新しい長さを超える要素は何でもかまいません。要素を指定すると、その要素のすべての出現箇所を配列から削除する必要があります。技術的にその要素を削除する必要はありません-たとえば、そうですか？

ヒント２

この要素のすべての出現箇所を配列の最後に移動できます。2つのポインタを使用してください！

ヒント３

さらに別の考え方は、削除される要素が存在しないと見なすことです。1回のパスで、表示されている要素をインプレースでコピーし続けると、この問題も解決するはずです。

考え方

1. 新規インデックスを作成 (nw_index)

2. ループを回す

3. 重複していなかったら新規インデックス番号にその値を代入する

• 解答コード

def removeElement(self, nums, val):
    nw_index = 0
    for x in nums:
        if x != val:
            nums[nw_index] = x
            nw_index += 1
    return nw_index

• Goでも書いてみます！

func removeElement(nums []int, val int) int {

    nw_index := 0
    for _, num := range nums {
        if num != val {
            nums[nw_index] = num
            nw_index++
        }
    }

    return nw_index
}

別解

class Solution:
    def removeElement(self, nums, val): 
        while val in nums:
            nums.remove(val)

手順説明

while val in nums でvalが含まれている回数ループを回して、remove関数でval要素を削除します。

remove関数は引数に対応する最初の要素一つを削除するために複数回ループを回して削除しています。