Contains Duplicate
整数の配列 nums が与えられます。いずれかの値が少なくとも2回出現する場合は true を、すべての値が異なる場合は false を返してください。
関数
- numsinteger-array
- 確認する整数
- 戻り値boolean
- true は、ある値が 2 回以上現れる場合、そうでなければ false
制約
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
例
- 入力
- nums = [3, 1, 4, 1, 5]
- 出力
- true
- 説明
- 値
1はインデックス 1 とインデックス 3 に現れるので、答えはtrueです。
- 入力
- nums = [2, 7, 1, 8]
- 出力
- false
- 説明
2、7、1、8は4つの異なる値なので、重複はありません。
- 入力
- nums = [-4, 4, 0]
- 出力
- false
- 説明
-4と4は絶対値が同じですが、異なる数であり、0は1回だけ現れるので、答えはfalseです。
提出時に隠しテスト+17件
発展問題
配列全体を常に読み込むのではなく、最初に重複する値を見つけた時点で停止できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての値をほかのすべての値と比較する方法は機能しますが、
10^4個の値では、比較の回数は約5 × 10^7回になります。すでに通過した値について、どんなことを覚えておけるでしょうか？繰り返しとは、現在の値が以前に出現したことのある値であることを意味します。ハッシュセットを使うと、「この値に出会ったことがあるか？」を平均定数時間で判定できます。
空の集合を使って配列を一度走査します。各値について、すでに集合に含まれていれば
trueを返し、そうでなければ追加します。ループが終了したら、すべての値が異なっていたことになります。
解説
重複とは、以前に見たことのある値のことです。ここで重要なのは、「これは見たことがあるか？」を素早く答えることです。すべてのペアを比較すれば答えはわかりますが、n = 10^4 の場合、比較回数は n(n-1)/2、つまり約 5 × 10^7 回になります。ソートすると同じ値が隣り合うようになり、ハッシュセットを使えば平均 O(1) で答えられるため、1回の走査で済みます。
並べ替えてから、隣り合う要素を比較する
考え方
ソート済みの配列では、同じ値は隣り合います。[3, 1, 4, 1, 5]をソートすると[1, 1, 3, 4, 5]になり、2つの1が隣り合います。そのため、ソート後は各値を直前の値とだけ比較すればよく、すべてのペアを試す場合に必要なn(n-1)/2回ではなく、n-1回の比較で済みます。
隣り合う値がどれも等しくなければ、配列のどこにも等しい値はありません。ソート順でxの2つのコピーの間にある値は、x以上かつx以下でなければならないため、それもまたxになるからです。
計算時間はソート処理が支配的で、O(n log n)です。numsをその場でソートすれば追加の配列は不要ですが、呼び出し元の入力の順序が変わります。それが許されない場合はコピーをソートし、その場合はO(n)の領域が必要です。
アルゴリズム
numsを昇順に並べ替えます。iを1から最後のインデックスまでループします。nums[i]がnums[i-1]と等しい場合は、trueを返します。- ループの後、
falseを返します。
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return Falseハッシュセットを使った1回の走査
考え方
配列を一度走査し、これまでに通過した値をすべてハッシュセットに保持します。値を追加する前に、その値がすでにセットにあるかどうかを確認します。[3, 1, 4, 1, 5]の場合、セットは{3, 1, 4}まで増え、2つ目の1が来たときには、セットにすでに含まれているので、5を読み取らずにtrueを返します。
セットには常に現在位置より前の値だけが格納されるため、一致が見つかれば現在の値が以前に現れたことを意味し、一致がないまま末尾に到達すれば、すべての値が異なることを意味します。
ハッシュセットの検索と挿入は平均してO(1)時間で行えるため、全体の走査はO(n)です。その代わりにメモリを使います。重複がなければ、セットには最終的にn個すべての値が格納されます。
アルゴリズム
- 空のハッシュセット
seenを作成します。 numsの各値について、それがseenに含まれている場合は、trueを返します。- そうでなければ、その値を
seenに追加します。 - ループの後、
falseを返します。
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
落とし穴と境界ケース
ロジックは単純なので、バグはループの境界や比較する内容にあります。
- 内側のループを
j = iから始めて、すべてのペアを比較する。すると、すべての値が自分自身と一致し、答えは常にtrueになります。 - 最初にソートせずに隣り合う要素を比較する。
[9, 1, 2, 3, 9]では、2つの9は隣り合っていません。 - 隣接要素を調べるループをインデックス0から始め、
nums[-1]を読み取る。1から始めれば、値が1つだけの配列は正しくfalseを返します。 - たとえば
abs(x)をハッシュ化して、絶対値が同じ値を等しいものとして扱う。-4と4は異なる数です。 x - yを返すC言語のソート用比較関数を書く。この場合、差は±2 × 10^9以内に収まり、intの上限2^31-1 = 2147483647より小さいため、たまたま範囲内に収まります。しかし、intの上限や下限に近い値ではオーバーフローし、ソート結果が誤ってしまいます。代わりに(x > y) - (x < y)を返してください。
よくある質問4
Contains Duplicate の時間計算量は何ですか？
ハッシュセットを使う解法は平均で O(n) 時間で実行され、追加の領域として O(n) を使用します。最初にソートする方法は O(n log n) 時間がかかり、入力の並べ替えが許される場合は追加の配列を必要としません。すべてのペアを比較する方法は O(n²) 時間がかかります。
追加の領域を使わずに Contains Duplicate を解けますか？
はい、配列の並べ替えが許されるなら、配列をその場でソートし、各値を隣の値と比較します。これにより、O(n) の集合を O(n log n) の時間と引き換えにできます。並べ替えをせず、追加メモリも使わない場合、残る選択肢は O(n²) のペアごとのチェックだけです。
ハッシュセットを使うと、なぜチェックが速くなるのでしょうか？
ハッシュセットは値をそのハッシュ値によって格納するため、値を保持しているかどうかの確認は、走査する代わりに平均して定数時間で行えます。各要素の処理に検索と挿入がそれぞれ1回必要なので、全体の処理は線形時間になります。
集合のサイズを配列の長さと比較するのは、有効な解決策ですか？
はい。nums全体から集合を作り、それが配列より小さいかどうかを確認すれば、O(n)の時間で正しい答えが得られます。ループを使う方法のほうが優れていることがよくあります。最初の重複に出会った時点で処理を終了する一方、集合を全体から作る方法では常にすべての値を読み取るためです。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def containsDuplicate(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [3, 1, 4, 1, 5]
期待値
true