（ブログ記事からの転載）
[https://leetcode.com/problems/remove-duplicates-from-sorted-array/]
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],
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:
Given nums = [0,0,1,1,1,2,2,3,3,4],
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.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
予め昇順にソートされた数値のリストを、重複を削除するように直接修正したリストを作成するという問題です。
入力のリストを直接修正するというのがポイントで、アウトプットのために別のリストを用意しない解法が求められています。
この問題はBad評価が多いのですが、おそらく以下が原因と思います。
入力のリストnumsに対して、関数の返り値はリストの要素数nで、正解を判定する対象はnums[:n]になる
なぜこういうややこしい設定にしたのか・・・問題文を最後まで読む力を試してるんですかね。
回答・解説
解法1
公式の解法はこちら。
入力のリストの要素数が0の場合は0を返しておきます。
iとjという2つの変数を作成し、これをポインタとして使います。
jはリストの要素数分ループを回すための通常のポインタで、iはリスト中の値が変わったときだけ+1し、リストの要素を新しい値で置き換えるためのポインタです。
このようにすることで、最後に正解を判定する対象nums[:i+1]が重複のない異なる値から構成されることになります。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0: return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
解法2
計算量は解法1が優れているのですが、正解を判定する対象はnums[:n]になるのがどうにも気に入らず、numsがそのまま正解判定対象になるように書いたのが以下です。
まあ私の意地みたいなコードなので、ご参考まで。
リストの初期の要素数分だけループを回し、重複する値はdelで削除していくという処理です。
class Solution:
def removeDuplicates(self, nums):
if len(nums) == 0: return 0
i = 1
for _ in range(1,len(nums)):
if nums[i] == nums[i-1]:
del nums[i]
else:
i += 1
return len(nums)