方針
numsを左から右へ走査し、次に残す値を書き込む位置を示すインデックスを保持します。現在の値がvalと異なる場合はnums[write]へコピーし、writeを進めます。valと等しい値は読み飛ばします。
各要素を処理する前、先頭のwrite個の位置には、これまでに確認した値のうちvalと異なるものだけが元の順序のまま正確に格納されています。writeは現在の走査位置を超えないため、残す値を書き込み位置へコピーしても、まだ読んでいない要素を上書きすることはありません。走査が終わると、writeが新しい長さとなり、nums[0..write)が順序を保ったフィルタ結果です。それ以降の配列部分は未規定なので、依存してはいけません。
時間計算量はO(N)、追加領域の計算量はO(1)です。
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int removeElement(int[] nums, int val) {
int write = 0;
for (int value : nums) {
if (value != val) {
nums[write++] = value;
}
}
return write;
}
}