スポンサーリンク

【LeetCode】27.Remove Element 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

 

問題

原文

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

内容

整数の配列numsと整数の変数valが与えられます。numsに含まれるすべてのvalをインプレイス処理で取り除いてください。nums内の各要素の相対的な順番は変わるかもしれません。

いくつかの言語では配列の長さを変えることはできないため、代わりに配列numsの初めの部分を処理結果で置き換える必要があります。具体的には、除外操作を行った後にk個の要素があれば、配列numsの最初のk個の要素は処理後の最終結果である必要があります。k個目を超えた要素の有無は問いません。

配列numsの最初のk個の要素を処理後の結果に置き換えてからkを返してください。

別の新たな配列を割り当ててはなりません。O(1)のメモリ空間(?)で、入力された配列のみを使ってインプレイス処理で進めてください。

補足

この問題はカスタムジャッジが用意されています。

※正しくない可能性があります。

方針

・配列numsを全探索

・numsの要素が整数valと一致していれば除外

・numsの要素が整数valと一致していなければ配列numsのk番目の要素にnumsの要素を代入し、kに1を加える

解答

解答1

配列numsのi番目の要素がvalと一致していた場合は、今回のループを終了して次のループへ進みます。そのため、nums[k] = nums[i]の操作を行いません。

配列numsのi番目の要素がvalと一致していなかった場合は、nums[k] = nums[i]の操作を行い、kに1を加えています。

解答2

for文の書き方を少し変えています。配列numsの各要素に対して処理を行います。

配列の要素を操作するかの判断を行う部分も、配列valと各要素が一致していたcontinueとするのではなく、配列の各要素がvalと一致していない場合のみ、配列numsの操作を行っています。

ただし、valと一致していた時の除外処理を行っていません。ジャッジが配列numsの最初のk個の要素を調べるだけで、k個目よりも先の要素について調べないから通るものであって、除外処理は本来行わないとダメかもしれません。

解答3

LeetCodeの仕様なのか、カスタムジャッジの影響なのかわかっていないのですが、returnでkを返したときは、配列numsの最初のk個目までの要素まで調べられるようです。そのためnumsの要素を操作する必要があります。

しかし、こちらの解答のようにreturnを行わなかった場合は、kの値のみがチェックされ、解答がAcceptされました。

配列nums内の操作をしていないので、このような形での解答は良くないと思うのですが、一応記載します。

考え方としては、配列numsの数だけループ処理を行い、numsにvalが含まれていれば、valを取り除いてkをインクリメントしています。

補足・参考・感想

LeetCodeを始めてまだ浅いので、特有の仕様や良い使い方を吸収して勉強していきたいと思います。

前:26. Remove Duplicates from Sorted Array

次:35. Search Insert Position

LeetCode 解答・解説記事一覧

コメント