26. Remove Duplicates from Sorted Array

ソート済みの、複数数字が重複する配列の中には一体何個の数字が含まれているかを考える問題。制約として、in-place で解く必要があります。たとえば、[1, 1, 2] という入力がされた場合、返り値は2で [1, 2, _] という順序の配列を返す必要があるということです。

leetcode.com

ただ、いまいち問題の意図がつかめず苦戦しました。単純に国語力の試される問題でもあります。実装は単純でした。

方針としては、

• i と i+1 (i は配列のインデックスとする) 、要するに隣同士の数字を比較し、右の値が左の値より大きければ入れ替えるという作業を繰り返します。
• 入れ替える作業が発生した場合、それは実質異なる数値を入れ替えることになるので、カウンターを1つ足します。

という作業を繰り返すだけで解くことができます。問題の意図が理解できれば捻りはとくになく素直な問題ではあります。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for i in range(len(nums)):
            if nums[k] < nums[i]:
                k += 1
                nums[k] = nums[i]
        return k + 1

時間計算量は O(n) でしょうか。与えられる配列の長さが増えると、その分だけループが多く回ることになります。

空間計算量は in-place な操作をしていることもあり O(1) になります。