Summary Ranges
異なる整数を含むソート済み配列 nums が与えられます。すべての値がちょうど1つの範囲に属するように、連続する整数の範囲に分割し、範囲の数を最小にしてください。範囲 a..b はテキスト "a->b" として表し、値が1つだけの場合は "a" として表します。範囲を昇順で返してください。
関数
- numsinteger-array
- 重複のない整数を並べ替えた配列
- 戻り値string-array
- 範囲をテキストとして、最小値から最大値の順に
制約
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsは昇順に並んでおり、重複はありません。
例
- 入力
- nums = [0, 1, 2, 5, 6, 9]
- 出力
- ["0->2", "5->6", "9"]
- 説明
0, 1, 2は連続しているため、"0->2"となります。2 から 5 への飛び越しで新しい範囲が始まり、"5->6"となります。また、9 は単独で"9"となります。
- 入力
- nums = [-3, -1, 0, 1, 4, 7, 8]
- 出力
- ["-3", "-1->1", "4", "7->8"]
- 説明
- -3 には隣接する値がありません（-2 がありません）。
-1, 0, 1は連続し、4 は単独で、7, 8はリストの末尾を形成します。負の値も同じように機能します。-1 の次は -1 + 1 = 0 です。
提出時に隠しテスト+16件
発展問題
numsに[1, 2, 2, 3]のような重複が含まれる場合を考えてみましょう。それでも"1->3"と表示されるようにするには、何を変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
配列はソートされています。隣り合う2つの値が同じ範囲に属するのはどのような場合ですか？
nums[i+1] == nums[i] + 1のときに限り、それらは連続しています。それ以外の隣り合う要素の組み合わせは、ある範囲の終わりと次の範囲の始まりを示します。現在の範囲がどこから始まったかを覚えておきます。次の値が現在の値より1大きい間は前に進みます。連続が途切れるか配列の末尾に達したら、開始位置から現在の値までの範囲を書き出し、次の範囲を次の値から始めます。
解説
すべての値の両隣を確認する
考え方
値を1つずつ見て、2つのことを確認します。ここで範囲が始まりますか？はい、これが最初の値であるか、直前の値が1小さくない場合です。ここで範囲が終わりますか？はい、これが最後の値であるか、直後の値が1大きくない場合です。
[0, 1, 2, 5, 6, 9]では、範囲は0、5、9で始まり、2、6、9で終わります。現在の範囲が始まった値を覚えておきます。範囲がnums[i]で終わるとき、"start->nums[i]"と書きます。ただし、9のように範囲が同じ値で始まり終わる場合は、"start"だけを書きます。
各値を1回ずつ調べ、隣り合う2つの値を確認するので、時間計算量はO(n)です。出力以外では、覚えておく開始値が1つだけなので、追加の領域計算量はO(1)です。
アルゴリズム
start = nums[0]を設定します。- 各インデックス
iについて、i > 0かつnums[i] != nums[i-1] + 1の場合、start = nums[i]を設定します。 iが最後のインデックスであるか、nums[i+1] != nums[i] + 1の場合、ここで範囲が終了します。start == nums[i]の場合は"start"を、そうでない場合は"start->nums[i]"を追加します。- 最後のインデックスの後にリストを返します。
def summaryRanges(nums):
n = len(nums)
ranges = []
start = nums[0]
for i in range(n):
# A range opens where the value before is not one less.
if i > 0 and nums[i] != nums[i - 1] + 1:
start = nums[i]
# A range closes where the value after is not one more.
if i == n - 1 or nums[i + 1] != nums[i] + 1:
ranges.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
return ranges各連続区間に対する2つのポインター
考え方
各範囲を配列のブロックとして扱い、その両端を見つけます。ポインター i は範囲の最初の値を指します。ポインター j は i から始まり、次の値がちょうど1大きい間は右へ進むため、範囲の最後の値で止まります。
[-3, -1, 0, 1, 4, 7, 8] の場合、-3 を指す i は範囲を延長できません。-1 は -2 ではないため、範囲は "-3" です。次に i が -1 に移り、j は 0 と 1 を越えて進み、4 の手前で止まります。範囲は "-1->1" です。その後は "4" と "7->8" です。各範囲の後、i は次の範囲の最初の値である j+1 に移ります。
範囲の数は可能な限り少なくなります。間にギャップがある2つの値が同じ範囲に含まれることはなく、この方法ではギャップの箇所でのみ分割されます。両方のポインターは前にしか進まないため、すべての範囲を通じて内側のループは合計で n 回実行され、時間計算量は O(n)、追加の空間計算量は O(1) になります。
アルゴリズム
i = 0を設定します。j = iを設定し、j+1 < nかつnums[j+1] == nums[j] + 1である間、jを右に進めます。i == jの場合は"nums[i]"を、それ以外の場合は"nums[i]->nums[j]"を追加します。i = j + 1を設定し、iが末尾を越えるまで繰り返します。- リストを返します。
def summaryRanges(nums):
ranges = []
n = len(nums)
i = 0
while i < n:
# i is the first value of a run; push j to its last value.
j = i
while j + 1 < n and nums[j + 1] == nums[j] + 1:
j += 1
ranges.append(str(nums[i]) if i == j else f"{nums[i]}->{nums[j]}")
# The next run starts right after this one.
i = j + 1
return ranges
落とし穴と境界ケース
ロジックは数行で済みます。間違いは端の部分にあります。
- 最後の範囲を忘れること。ギャップに出会ったときだけ範囲を書き出すループでは、最後の範囲が書き出されません。そのため、
[0, 1, 2, 5, 6, 9]では"9"が失われます。最後のインデックスでも範囲を閉じましょう。 - 単一の値に
"a->a"と書くこと。値が1つの範囲は"a"と書きます。 - 大きな値を指数表記で出力すること。Rでは
1000000000のようなdoubleが1e+09に変換されます。貼り付ける前に値を整数に変換しましょう。
よくある質問4
Summary Ranges の時間計算量はどれくらいですか？
O(n)。各値を1回ずつ確認し、各範囲を1回ずつ書き込みます。出力リストを除けば、追加の領域は O(1) です。現在の範囲の開始位置と、1つか2つのインデックスだけです。
なぜすべての間隔で区切ると、範囲の数が最も少なくなるのでしょうか？
範囲には連続する整数が含まれるため、その間の数が抜けた2つの値を含めることはできません。したがって、ソート済み配列の各隙間で範囲を分ける必要があり、隙間がg個ある場合、少なくともg+1個の範囲が必要です。隙間の位置だけで分割すると、ちょうどg+1個になります。
数値が1つだけの範囲は、どのように扱いますか？
範囲の開始値と終了値が同じかどうかを確認します。同じ場合は、"9"のようにその値だけを書きます。同じでない場合は、"5->6"のように開始値、矢印、終了値を書きます。2つのポインターを使う場合、判定式はi == jです。
Summary Ranges では入力をソートする必要がありますか？
はい。このメソッドは隣り合う要素だけを比較するため、連続する整数が隣り合っていることを前提としています。入力がソートされていない場合は、まずソートすると、タスク全体の計算量は O(n log n) になります。または、値をハッシュセットに入れ、最長連続列の問題と同様に、各範囲を最小値から伸ばしていきます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def summaryRanges(nums):
# ここにコードを記述してくださいケース1
ケース2
入力
nums = [0, 1, 2, 5, 6, 9]
期待値
["0->2", "5->6", "9"]