ゼロから始めるLeetCode Day14「26. Remove Duplicates from Sorted Array」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。

LeetCode

問題

26. Remove Duplicates from Sorted Array

昇順ソートされた整数配列numsから重複しない要素の数を返す問題。

Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,,,,,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:
1 <= nums.length <= 3 * $10^4$
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

解法

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0

        for j in range(1, len(nums)):
            if nums[i] != nums[j]:
                i += 1
                nums[i] = nums[j]
        
        return i + 1

重複しない要素数のカウント

for j in range(1, len(nums)):
    if nums[i] != nums[j]:
        i += 1
        nums[i] = nums[j]

return i + 1

for j in range(1, len(nums))
インデックス 1 からリストの末尾までを順に見ていく。
変数jは、リスト nums の現在の要素を反復処理するためのポインタである。

if nums[i] != nums[j]:
nums[i]　と nums[j]（現在見ている要素）が異なるかどうかをチェックする。

i += 1
新しい要素を格納するための次の位置を指定する。

nums[i] = nums[j]
nums[j] の要素（新しい一意な要素）を nums[i] の位置にコピーします。これにより、重複が削除された要素が nums の先頭に詰めて格納されていきます。

例

nums = [0,0,1,1,1,2,2,3,3,4]

j	i (処理開始時)	nums の状態 (処理後)
1	0	[0,0,1,1,1,2,2,3,3,4]
2	0	[0,1,1,1,1,2,2,3,3,4]
3	1	[0,1,1,1,1,2,2,3,3,4]
4	1	[0,1,1,1,1,2,2,3,3,4]
5	1	[0,1,2,1,1,2,2,3,3,4]
6	2	[0,1,2,1,1,2,2,3,3,4]
7	2	[0,1,2,3,1,2,2,3,3,4]
8	3	[0,1,2,3,1,2,2,3,3,4]
9	3	[0,1,2,3,4,2,2,3,3,4]

最終的に重複しない要素数はi + 1で4となる。