Longest Consecutive Sequence
整数配列 nums が順不同で与えられます。連続するシーケンスとは、nums 内のどこかにそれぞれ存在する x、x+1、x+2 などの値の集まりです。最長の連続シーケンスの長さを返してください。複数回出現する値も1回として数えます。
関数
- numsinteger-array
- 整数は順不同で、重複可
- 戻り値integer
- nums に含まれる連続した値の最長連続列の長さ
制約
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 値は重複していてもかまいません。配列内の位置は重要ではなく、どの値が含まれているかだけが重要です。
例
- 入力
- nums = [40, 4, 39, 1, 3, 2, 41]
- 出力
- 4
- 説明
1、2、3、4はすべて含まれており、配列の中に散らばっているにもかかわらず、4つ連続しています。もう一方の連続した値39から41までは、3つの値しかありません。
- 入力
- nums = [7, 3, 7, 5, 6, 5]
- 出力
- 3
- 説明
5、6、7で3つの連続した数になります。2つ目の7と2つ目の5は何も追加せず、4がないため3は加われません。
- 入力
- nums = [10, 30, 20]
- 出力
- 1
- 説明
- 差が1である2つの値はないため、各連続部分は単一の値を保持し、答えは1です。
発展問題
値が一つずつ届き、そのたびにこれまでで最も長い連続区間を報告しなければならないとします。値ごとに平均 O(1) 時間で答えを最新の状態に保てますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数列の最初の数としてあらゆる値を試し、そこから数を増やしていきましょう。何度も繰り返し尋ねる質問は何ですか。また、配列からその値を探すとき、答えを得るたびにどれだけのコストがかかりますか？
質問は「
x+1は配列に含まれているか？」です。ハッシュセットなら平均して定数時間で答えられ、重複も取り除けます。x-1が集合に含まれていない値xからのみ数え始めます。そこからx+1、x+2と進み、集合に含まれている間は続けて、最も長い連続列を保持します。これにより、各値は1つの連続列でのみ数えられます。
解説
連続する値は配列のどこにあってもかまいません。ソートすると、O(n log n) で順番に並べられます。ハッシュセットを使えば、「x+1 はあるか？」を O(1) で確認でき、x-1 が存在しない値からのみ数え始めれば、各値を調べるのは1回だけです。合計で O(n) となります。
配列を検索して、すべての値から順に数え上げる
正しいが、最大のテストでは終わらない
考え方
すべての値を連続列の開始点の候補として扱います。xから、配列内でx+1、次にx+2を探し、値が見つからなくなるまで続けて、最も長い個数を保持します。すべての連続列にはnums内に最小の値があり、ループはその値から連続列全体をたどります。
各検索では最大n個の値を読み取り、長い連続列はその各要素から再びたどられます。シャッフルされた1つの連続列を構成する10^4個の値では、走査に約n²/2 = 5 × 10^7ステップかかり、各回で平均して配列の半分を調べるため、比較回数は約2.5 × 10^11になります。
アルゴリズム
bestを 0 に設定します。numsの各値startについて、currentをstartに、lengthを 1 に設定します。numsを走査してcurrent+1が見つかったら、currentとlengthに 1 を加えます。lengthのほうが大きければ、その値をbestに格納します。bestを返します。
def longestConsecutive(nums):
best = 0
for start in nums:
current = start
length = 1
# "in" on a list reads it from the front until it finds the value.
while current + 1 in nums:
current += 1
length += 1
best = max(best, length)
return best並べ替えてから、連続する区間を数える
考え方
ソートすると、各連続区間の値が隣り合います。[40, 4, 39, 1, 3, 2, 41] は [1, 2, 3, 4, 39, 40, 41] になり、連続区間は左から右へ読み取れます。
ソート済みの値を順に見て、現在の連続区間の長さを保持します。直前の値より1大きい値が続く場合は、連続区間が延長されます。同じ値が繰り返された場合は、連続区間は延長も終了もしないため、スキップします。それ以外の値が現れたら、長さ1の新しい連続区間が始まります。
ソートの計算量は O(n log n)、走査の計算量は O(n) です。インプレースでソートすれば追加の配列は不要です。コピーをソートする言語では、O(n) のメモリを使用します。
アルゴリズム
numsを昇順に並べ替える。- 配列は空でないため、
bestとrunを1に設定する。 - インデックス
iを1から順に調べ、nums[i]がnums[i-1]と等しい場合はスキップする。 nums[i]がnums[i-1]+1なら、runに1を加える。それ以外の場合はrunを1に設定する。runがより大きければ、その値をbestに保存する。bestを返す。
def longestConsecutive(nums):
nums.sort()
best = 1
run = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue # a repeat neither extends nor breaks the run
if nums[i] == nums[i - 1] + 1:
run += 1
else:
run = 1
best = max(best, run)
return best各実行の開始からのみカウントするハッシュセット
考え方
ハッシュセット内の各値に対するメンバーシップ確認は平均で O(1) のコストで済み、重複した値は1つのエントリにまとめられます。
すべての値から順に調べると、処理が重複します。1, 2, 3, 4 の並びでは、1 からは3ステップ、2 からは2ステップ、3 からは1ステップ進むことになります。そこで、連続する値の並びの先頭からだけ調べます。つまり、x-1 が存在しない値 x から始めます。例1では、条件を満たすのは 1 と 39 だけなので、長さ4と3の並びが得られます。
各値は1つの並びに属し、その並びを調べるときにだけ処理されるため、すべての探索を合わせてもステップ数は最大で n です。各値につき確認が1回なので、合計の計算時間は O(n)、セットに必要なメモリは O(n) です。
アルゴリズム
numsのすべての値をハッシュセットvaluesに入れ、bestを 0 に設定します。- セット内の各値
xについて、x-1がセット内にある場合はスキップします。これは連続する値の並びの先頭ではありません。 - そうでなければ、
endをxに設定し、end+1がセット内にある間、endに 1 を加えます。 end-x+1がより大きい場合は、それをbestに格納します。bestを返します。
def longestConsecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only a value with no left neighbour starts a run.
if value - 1 in values:
continue
end = value
while end + 1 in values:
end += 1
best = max(best, end - value + 1)
return best
落とし穴と境界ケース
- ソート後に、重複を途切れとして扱ったり、1ステップとして数えたりすること。
[1, 2, 2, 3]で、2つ目の2で連続区間をリセットすると答えは2になり、1ステップとして数えると4になります。正解は3です。 - ソート済みの列を走査するとき、
bestを0で初期化し、ループ内でしか更新しないこと。この場合、要素が1つだけの配列は1ではなく0を返します。 - 連続区間の開始位置からだけではなく、集合のすべての値から走査すること。すると、
10^4個の値からなる1つの連続区間を走査するのに、5 × 10^7ステップかかります。 - 集合ではなく
numsをループすること。2,500個の連続区間の先頭の値が2,000回現れる場合、その区間を2,000回走査することになります。 - 値をインデックスとして配列にアクセスすること。値は
±10^9に達するため、2 × 10^9個の要素が必要になります。
よくある質問3
最長連続シーケンスの時間計算量はどのくらいですか？
ハッシュセットを使う解法は、平均で O(n) 時間、追加メモリ O(n) で実行できます。ソートと連続数のカウントには O(n log n) かかります。セットを使わずに次の値を毎回配列から検索すると、最大で O(n³) かかります。
追加のメモリを使わずに最長連続シーケンスを解けますか？
はい、入力の順序を変更してよいなら、入力をその場でソートし、重複を飛ばしながら1回の走査で連続する値の数を数えます。追加メモリはO(1)ですが、時間計算量はO(n log n)です。O(n)の解法にはハッシュセットが必要です。
Union-Find で最長連続シーケンス問題を解ける？
はい。それぞれの異なる値を集合にし、両方が存在する場合はxとx+1を結合して、最大の集合のサイズを返します。ほぼO(n)時間で実行できますが、値からインデックスへのマップ、親リンク、サイズが必要です。一方、ハッシュセットを走査する方法で必要なのは1つの集合です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestConsecutive(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [40, 4, 39, 1, 3, 2, 41]
期待される出力
4