Remove Duplicates from Sorted Array
整数の配列 nums が非減少順に並べられているため、等しい値は隣り合っています。nums の異なる値を、それぞれ一度ずつ、現れる順に返してください。たとえば、[2, 2, 5] の場合は [2, 5] となります。
関数
- numsinteger-array
- 整数を非減少順に並べたもの
- 戻り値integer-array
- nums の異なる値を昇順に並べたもの
制約
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104numsは非減少順にソートされています。
例
- 入力
- nums = [1, 1, 2, 3, 3, 3]
- 出力
- [1, 2, 3]
- 説明
1が2回、3が3回登場します。それぞれ1つずつ残すと、[1, 2, 3]になります。
- 入力
- nums = [-2, 0, 0, 5]
- 出力
- [-2, 0, 5]
- 説明
0だけが繰り返されます。負の値も同じように機能するため、答えは[-2, 0, 5]です。
- 入力
- nums = [7, 7, 7]
- 出力
- [7]
- 説明
- すべての値は
7なので、残っているのは7だけです。
提出時に隠しテスト+15件
発展問題
numsを別の配列に格納するのではなく、インプレースで書き換えることで、追加メモリをO(1)にできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
numsはソートされているため、同じ値のコピーはすべて1つの連続した並びになります。これまでに見た値をすべて記憶せずに、ある値がその並びの最初だとどうすれば判断できますか？値は、保持した最後の値と異なる場合に限り、新しい連続区間の開始となります。つまり、比較する値は常に1つだけで、処理を進めながら配列の先頭から上書きできます。
書き込みインデックス
kを保持します。nums[0]は常に保持されるため、1 から開始します。その後の値をすべて読み取り、nums[k-1]と異なる場合は、それをnums[k]にコピーしてkに 1 を加えます。最初のk個の値を返します。
解説
任意の配列から重複を削除するには、これまでに見たすべての値を記憶しておく必要があります。入力がソート済みなら、その必要はありません。同じ値は隣り合うため、最後に保持した値と異なるときに限り、新しい値だと判断できます。これにより、追加のメモリを使わず、2つのインデックスで1回走査するだけで処理できます。
ハッシュセット内の既出の値を記録する
考え方
numsを順に見ていき、すでに答えに追加した値を集合に記録します。値が集合に含まれていなければ、答えに追加して集合にも加えます。含まれていれば、スキップします。[1, 1, 2, 3, 3, 3]の場合、答えは[1]、次に[1, 2]、そして[1, 2, 3]となり、その後に現れる重複はすべてスキップされます。
各値は最初に現れたときに一度だけ、出会った順に追加されるため、答えは正しくなります。この方法ではnumsがソート済みであるという性質を一切利用しないので、どのような配列でも機能します。
集合の検索は平均してO(1)で行えるため、この処理は時間計算量がO(n)です。ただし、集合と答えはそれぞれ最大でn個の値を保持できるため、追加の空間計算量はO(n)です。Cでは組み込みの集合がないため、あり得る2 × 10^4 + 1個の値に対するフラグの配列で同じ処理ができます。
アルゴリズム
- 空の集合
seenと空のリストresultを作成します。 numsの各値について、それがseenに含まれているか確認します。- 含まれていない場合は、それを
seenに追加し、resultに追加します。 resultを返します。
def removeDuplicates(nums):
seen = set()
result = []
for num in nums:
if num not in seen:
seen.add(num)
result.append(num)
return result書き込みポインターを使ってその場でコンパクト化する
考え方
ソート済みの入力では、ある値のコピーはすべて1つの連続した並びを作るため、値を保持するのは、直前に保持した値と異なる場合に限られます。必要なのは比較1回で、集合は不要です。
2つのインデックスを使います。読み取りインデックス i はすべての値を順に見ていきます。書き込みインデックス k は保持済み部分の末尾を示します。つまり、nums[0] から nums[k-1] には、これまでに見つかった重複のない値が常に格納されています。最初の値は必ず保持するので、k = 1 から始めます。nums[i] が nums[k-1] と異なるときは、それを nums[k] にコピーして、k を進めます。
[1, 1, 2, 3, 3, 3] の場合：i = 1 は2つ目の 1 を読み取りますが、何も起こりません。i = 2 は 2 を読み取り、これは nums[0] = 1 と異なるため、インデックス1に格納され、k は2になります。i = 3 は 3 をインデックス2に書き込み、k は3になります。最後の2つの 3 は nums[2] と一致するため、スキップされます。最初の3つの要素は [1, 2, 3] になります。
書き込み位置が読み取り位置を追い越すことはありません。k は常に i 以下なので、読み取る前に値を上書きすることはありません。1回の走査にかかる時間は O(n) で、返される値を除けば使うのは2つの整数だけです。追加の空間は O(1) です。
アルゴリズム
k = 1に設定します。nums[0]は常に保持されます。iを1から最後のインデックスまでループします。nums[i]がnums[k-1]と異なる場合、nums[k] = nums[i]に設定し、kに1を加えます。numsの最初のk個の値を返します。
def removeDuplicates(nums):
# nums[0:k] holds the distinct values found so far, in order.
k = 1
for i in range(1, len(nums)):
if nums[i] != nums[k - 1]:
nums[k] = nums[i]
k += 1
return nums[:k]
落とし穴と境界ケース
書き込みポインタは短く、そのバグはどの値と比較するかに関するものです。
iが最後のインデックスまで進むのに、nums[i]とnums[i+1]を比較する。最後の比較では、配列の末尾を1つ越えた位置を読み取ります。kを0から始める。すると最初の値がnums[-1]と比較されます。これは範囲外の値で、Pythonでは最後の要素です。- 最初の
k個の値ではなく、配列全体を返す。末尾には古い値が残っているため、[1, 1, 2]は[1, 2, 2]として返されます。 - ハッシュセットを反復処理して答えを作る。ほとんどの言語ではハッシュセットに順序がないため、値の順序がばらばらになることがあります。代わりに、各値に初めて出会ったときにリストに追加します。
- LuaとRでは、配列のインデックスは1から始まります。保持する部分は
nums[1]からnums[k]までで、比較対象はnums[k-1]ではなくnums[k]です。
よくある質問4
ソート済み配列から重複を削除する処理の時間計算量は何ですか？
書き込みポインターを使う解法では各値を1回ずつ読み取るため、実行時間は O(n) です。返す値のほかに、追加の領域として2つのインデックス分の O(1) を使用します。
なぜ配列をソートする必要があるのでしょうか？
ソートすると、同じ値のコピーはすべて1つの連続した並びにまとまるため、値が新しいのは、最後に保持した値と異なる場合に限られます。ソートされていない配列では、ある値のコピーが最初の出現箇所から大きく離れた位置に現れることがあり、これまでに見たすべての値を記憶するためにハッシュセットが必要となり、そのために追加の空間 O(n) がかかります。
追加のメモリを使わずにインプレースで重複を削除するにはどうすればよいですか？
読み取りインデックスの隣に書き込みインデックス k を保持します。最初の k 個のスロットには、これまでに確認した重複のない値が格納されています。読み取った値が nums[k-1] と異なる場合は、それを nums[k] にコピーし、k を進めます。書き込みインデックスが読み取りインデックスを超えることはないため、読み取る前に値が上書きされることはありません。
各値を最大 2 回まで許可するにはどうすればよいでしょうか？
1つ前ではなく、保持部分の2つ前の値と比較します。k < 2の場合、またはnums[i]がnums[k-2]と異なる場合は、nums[i]をコピーします。nums[k-2]と等しい場合、保持部分の末尾にはすでにその値が2つあります。同じ考え方で、nums[k-m]を使えば最大m個まで保持できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def removeDuplicates(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [1, 1, 2, 3, 3, 3]
期待値
[1, 2, 3]