LeetCodeに毎日挑戦してみた26. Remove Duplicates from Sorted Array （Python、Go）

はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

8問目（問題26)

26. Remove Duplicates from Sorted Array

問題内容(日本語訳)

並べ替えられた配列numsを指定して、各要素が1*回*だけ表示され、新しい長さを返すように、重複をインプレースで削除します。

別の配列に余分なスペースを割り当てないでください。O（1）の余分なメモリを使用して入力配列をインプレースで変更する必要があります。

明確化：

戻り値が整数であるのに、答えが配列である理由がわかりませんか？

入力配列は参照によって渡されることに注意してください。これは、入力配列への変更が呼び出し元にも認識されることを意味します。

内部的には、これについて考えることができます。
// numsは参照によって渡されます。（つまり、コピーを作成せずに）
int len = removeDuplicates（nums）;

//関数内のnumsへの変更は、呼び出し元に認識されます。
//関数から返された長さを使用して、最初のlen要素を出力します。
for（int i = 0; i <len; i ++）{
    print（nums [i]）;
}

Example 1:

  Input: nums = [1,1,2]
  Output: 2, nums = [1,2]
  Explanation: 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:

  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 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.

ヒント1

この問題で焦点を当てる重要なポイントは、ソートされる入力配列です。重複する要素に関する限り、特定の配列が並べ替えられたときの配列内でのそれらの位置は何ですか？答えは上の画像を見てください。要素の1つの位置がわかっている場合、重複するすべての要素の位置もわかっていますか？

ヒント2

配列をインプレースで変更する必要があり、最終的な配列のサイズは入力配列のサイズよりも小さくなる可能性があります。したがって、ここでは2ポインターアプローチを使用する必要があります。1つは、元の配列の現在の要素を追跡し、もう1つは一意の要素のみを追跡します。

ヒント3

基本的に、要素が検出されたら、その重複をバイパスして、次の一意の要素に進む必要があります。

考え方

新規インデックスを作成 (nw_index)
len(nums)回ループを回して重複していたらそのまま進める
重複していなかったら新規インデックスの番号にその値を代入する
戻り値は長さを返すのでプラス1します

解答コード

  class Solution(object):
      def removeDuplicates(self, nums):
          nw_index = 0
          for i in range(len(nums)):
              if nums[nw_index] != nums[i]:
                  nw_index +=1
                  nums[nw_index] = nums[i]
          return (nw_index + 1)

Goでも書いてみます！

func removeDuplicates(nums []int) int {
    nw_index := 0
    for _, num := range nums {
        if nums[nw_index] != num {
            nw_index++
            nums[nw_index] = num
        }
    }

    return (nw_index + 1)
}

別解

def removeDuplicates(self, nums):
    nums[:] = sorted(set(nums))
    return len(nums)

手順説明

set() でset型（集合型）に変換します

set型とは？

set型は重複しない要素（同じ値ではない要素、ユニークな要素）のコレクションで、和集合、積集合、差集合などの集合演算を行うことができる。

setは集合なので順番がぐちゃぐちゃになりますのでsorted関数で昇順に戻します

nums[:]に参照を代入します。ここでnums=にしないのは新たにオブジェクトを生成してメモリを消費しないためです