# LeetCode Easy 26. Remove Duplicates from Sorted Array

tags: leetcode

問題

• Explore
• Problems

アイデア

｢ソートされた配列から同じ要素を取り除いたサイトの配列の大きさを返せ｣という問題です．

ただし，in-placeなアルゴリズムにせよとのこと．つまり$O(1)$で解く必要があります．

整列されているという特徴を活かした問題を解いていきます．

解法

• 最後に参照した要素をlast_numとして保存します．
• 配列で現在見ている要素を指す添字をcur_posとし，この要素がlast_numと同じか，違うかで分岐させます．

計算量

配列の大きさを$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cur_pos = 0
        last_num = None
        while cur_pos < len(nums):
            if nums[cur_pos] == last_num:
                nums.pop(cur_pos)
            else:
                last_num = nums[cur_pos]
                cur_pos += 1
                
        return cur_pos