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つの値だけで構成され、答えは1です。
提出時に隠しテスト+17件
発展問題
値が1つずつ届き、そのたびにこれまでの最長連続部分を報告しなければならないとします。値ごとの平均時間 O(1) で答えを最新の状態に保てますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数列の最初の数としてすべての値を試し、順に数を増やしていきましょう。何度も繰り返し尋ねる質問は何でしょうか。また、配列からその値を探すとき、回答ごとにどれくらいのコストがかかるでしょうか。
質問は「
x+1は配列に含まれているか？」です。ハッシュセットなら平均して定数時間で答えられ、重複も取り除けます。その
x-1が集合に含まれていない値xからだけ数え始めます。そこからx+1、x+2と進み、集合に含まれている間は続けて、最も長い連続列を記録します。こうすれば、各値は1つの連続列でしか数えられません。
解説
連続列の値は配列内のどこにでもあるため、左から右へ順に連続列を読み取ることはできません。ソートすれば、値を O(n log n) で並べられます。ハッシュセットならさらに効率的です。x+1 があるかどうかを O(1) で調べられ、x-1 が存在しない値からのみ数え始めれば、各値を一度ずつ調べるだけで済むため、探索全体は O(n) になります。
配列を検索して、すべての値からカウントアップする
正しいが、最大のテストでは終わらない
考え方
すべての値を、連続列の開始候補として扱います。xから始めて、配列の中にx+1があるか探します。あれば、x+2を探し、値が見つからなくなるまで続けます。たどり着いた値の数がxから始まる連続列の長さで、その中で最大の長さが答えです。
この方法が正しいのは、すべての連続列には最小の値があり、その値はnumsに含まれているためです。ループはその値を開始点として試し、連続列全体をたどります。重複があっても問題ありません。同じ開始点を2回試すだけです。
この方法は2つの点で遅くなります。「そこにあるか？」を確認するたびに最大で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 から 4 まで進み、その後 39 へ飛びます。
ソート済みの値を順に確認し、現在の連続範囲の長さを保持します。前の値より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に保存します。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各実行の開始時点からのみカウントするハッシュセット
考え方
すべての値をハッシュセットに入れます。すると、「x+1 は存在するか？」の確認は、走査する代わりに平均 O(1) で済み、重複した値は1つのエントリにまとめられます。
すべての値から順にたどると、処理が重複します。たとえば 1, 2, 3, 4 の並びでは、1 から3ステップ、2 から2ステップ、3 から1ステップ進むことになります。そこで、連続した並びの最初の値からだけたどります。値 x が最初の値となるのは、x-1 がセットに含まれていない場合に限ります。[40, 4, 39, 1, 3, 2, 41] では、該当するのは 1 と 39 だけです。1 からは長さ4の並びである 4 までたどり、39 からは長さ3の並びである 41 までたどります。
各値はちょうど1つの連続した並びに属し、その並びの最初の値からたどる場合にだけ、その値を通過します。そのため、すべての走査を合わせてもステップ数は最大で n です。各値につき1回の所属確認とセットの構築を加えると、セットに O(n) のメモリを使い、合計の時間計算量は O(n) です。
nums ではなく、セットをループします。2,500個の値からなる連続した並びの最初の値が nums に2,000回含まれている場合、nums をループすると、その並びを2,000回たどることになります。
アルゴリズム
numsのすべての値をハッシュセットvaluesに入れ、bestを 0 に設定します。- セット内の各値
xについて、x-1がセット内にある場合はスキップします。これは連続する値の並びの先頭ではありません。 - そうでなければ、
endをxに設定し、end+1がセット内にある間、endに 1 を加えます。 end-x+1がbestより大きければ、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をループする。何千回も出現する値から始まる連続区間を、何千回もたどることになります。 - 値をインデックスにした配列で値を記録する。値は
±10^9に達するため、配列には2 × 10^9個の要素が必要になります。
よくある質問4
Longest Consecutive Sequence の時間計算量は何ですか？
ハッシュセットを使う解法は、平均で O(n) 時間で実行され、追加メモリとして O(n) を使用します。ソートしてから連続する値を数える方法は、O(n log n) 時間かかります。セットを使わずに、次の値を配列から検索する方法では、最大で O(n³) かかります。
forループの中にwhileループがあるのに、なぜハッシュセットを使った解法はO(n)なのですか？
内側のループは、左隣の値 x-1 が存在しない値、つまり連続する並びの最初の値からのみ実行されます。各値は、その値が属する並びの走査によってのみ処理され、ほかの走査では処理されないため、内側のループ全体でのステップ数は最大でも n です。外側のループでは値ごとにチェックを1回行うため、合計で O(n) となります。
追加のメモリを使わずに、最長連続シーケンスを解けますか？
はい、入力を並べ替えてもよいなら、入力をその場でソートし、重複をスキップしながら1回の走査で連続する範囲を数えます。これなら追加メモリは O(1) ですが、時間計算量は O(n log n) です。O(n) の解法にはハッシュセットが必要です。
Union-Findで最長連続シーケンスを解けるでしょうか？
はい。それぞれの異なる値を集合にし、xとx+1の両方が存在する場合はそれらを結合し、最大の集合のサイズを返します。ほぼO(n)の時間で実行できますが、値からインデックスへのマップ、親リンク、サイズが必要です。一方、ハッシュセットを走査する方法なら、1つのセットと2つのループで同じ処理ができます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def longestConsecutive(nums):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [40, 4, 39, 1, 3, 2, 41]
期待値
4