ゼロから始めるLeetCode Day15「27. Remove Element」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。

LeetCode

問題

27. Remove Element

整数配列numsと整数valがある。
この配列numsから、値がvalと等しい要素をすべて削除する。
その後、valの値を削除したnumsの要素数を返す。

Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]

Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,,,_]

Constraints:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        non_val_index = 0

        for i in range(len(nums)):
            if nums[i] != val:
                nums[non_val_index] = nums[i]
                non_val_index += 1

        return non_val_index

valと一致しない値のカウント

if nums[i] != val
削除したい値valと異なる場合にのみ、以下の処理が実行される。

nums[non_val_index] = nums[i]
もしnums[i]がvalと異なる場合、その要素をnon_val_indexが指す位置にコピーする。

non_val_index += 1
valではない要素を一つ配置したので、次のvalではない要素を配置する位置を一つ進める。

例

Input: nums = [3,2,2,3], val = 3

i	nums[i] != val nums (リストの状態)	non_val_index
0	false→[3, 2, 2, 3]	0
1	true→[2, 2, 2, 3]	1
2	ture→[2, 2, 2, 3]	2
3	false→[2, 2, 2, 3]	2

最終的な重複のない要素数として2が返却される。