Next Permutation
整数の配列 nums が与えられます。値は重複する場合があります。これらの値の異なる並べ替えをすべて辞書順に並べたものを考えてください。2つの並べ替えを比較するときは、値が異なる最初のインデックスを比べ、その位置の値が小さい方を先にします。この順序で nums の直後にくる並べ替えを返してください。
nums がすでに最大の並べ替えである場合、その後に並べ替えはありません。その場合は、値を昇順に並べた最小の並べ替えを返してください。時間計算量 O(n)、追加メモリ O(1) を目指してください。
関数
- numsinteger-array
- 値の現在の並び
- 戻り値integer-array
- 辞書順で次の並び、または nums が最大の場合は、値を昇順に並べたもの
制約
1 ≤ nums.length ≤ 50000 ≤ nums[i] ≤ 1000
例
- 入力
- nums = [2, 5, 4, 1]
- 出力
- [4, 1, 2, 5]
- 説明
- 末尾の
5, 4, 1は降順なので、その前にある 2 を大きくする必要があります。2 より大きい末尾の値のうち最小のものは 4 です。そこに置き、残りを昇順に並べます:[4, 1, 2, 5]。
- 入力
- nums = [3, 2, 2, 1]
- 出力
- [1, 2, 2, 3]
- 説明
- 配列全体が降順になっているため、3、2、2、1の最大の並びです。答えは最小の並びである
[1, 2, 2, 3]に戻ります。
- 入力
- nums = [1, 5, 1]
- 出力
- [5, 1, 1]
- 説明
- 最初の1は大きくならなければなりません。最後の1はそれと等しく、大きくはないため、その位置に入ることができる値は5だけで、結果は
[5, 1, 1]になります。
発展問題
代わりに、辞書順でnumsの直前に来る、ひとつ前の並びをどのように見つけますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
配列を少し大きくするには、できるだけ右側まで変更します。配列の接尾部分は、その部分の値だけを並べ替えても、これ以上大きくできないのはどのようなときですか？
値が上がり続ける間、右から進みます。その後の値より小さい最初の値がピボットです。そこは増加できる最も右の位置です。その後はすべて下降しています。
ピボットを、それより後ろにある値のうち、右端の厳密に大きい値と入れ替えます。ピボットより後ろの部分はまだ降順なので、反転してできるだけ小さくします。ピボットがなければ、配列全体を反転します。
解説
降順の接尾部は、その値で可能な限り大きくなっているため、次の並びではその直前の値、つまりピボットを変更します。ピボットを可能な限り小さい量だけ増やし、その後、接尾部を可能な限り小さくします。これには、右側からの走査を2回と、配列内での反転が1回必要です。
順序どおりに並べたリスト
正しいが、最大のテストでは終わらない
考え方
ソート済みの値から深さ優先で並べ方を構築し、常に未使用の最小の値から試します。これにより辞書順に生成されるため、numsより厳密に大きい最初の並べ方が答えです。なければ、ソート済みの値を返します。重複する値があると、[1, 1, 5]の場合の115、151、115、151、511、511のように、一部の並べ方が2回構築されますが、重複したものは先に構築した並べ方を繰り返すだけなので、最初に見つかるより大きな並べ方が次の並べ方であることに変わりはありません。
個数はn!のように増加します。異なる値が12個ある場合、並べ方は479,001,600通りあります。
アルゴリズム
numsのコピーをソートしてpoolに格納します。poolの未使用の要素を左から順に選び、深さ優先で並びを構築します。- 並びが完成したら、位置ごとに
numsと比較します。 numsより大きい最初の並びを返します。- それより大きいものがなければ、
poolを返します。
def nextPermutation(nums):
n = len(nums)
pool = sorted(nums) # taking the smallest unused value first gives sorted order
used = [False] * n
current = []
def build():
# True once current holds the first arrangement greater than nums
if len(current) == n:
return current > nums # Python compares lists in dictionary order
for i in range(n):
if not used[i]:
used[i] = True
current.append(pool[i])
if build():
return True
current.pop()
used[i] = False
return False
if build():
return current
return pool # nothing is greater: nums was the largest arrangementピボットを見つけ、入れ替え、接尾辞を反転する
考え方
ピボットは、右隣の値より小さい、右から見て最初の値です。[2, 5, 4, 1]では2です。これは増加させられる最も右の位置であり、可能な限り右端の位置を増加させることで、増加幅を最小に保てます。
ピボットより厳密に大きいサフィックス内の最小値とピボットを入れ替えます。サフィックスは降順なので、それはピボットより大きい値のうち最も右にある値、つまり4です。その結果、[4, 5, 2, 1]になります。古いピボットは4があった位置に収まるため、サフィックスは引き続き降順です。先頭の値が大きくなったので、サフィックスは可能な限り小さく、昇順にする必要があります。降順の並びを反転すればそうなります。[4, 1, 2, 5]。
ピボットがない場合、配列は最大の並びであり、全体を反転すると最小になります。各ステップは1回の走査または1回の反転なので、時間計算量はO(n)、メモリ計算量はO(1)ですが、R版はO(n)のコピーを返します。
アルゴリズム
iをn-2に設定し、nums[i] ≥ nums[i + 1]の間、左に移動させます。i ≥ 0の場合、jをn-1に設定し、nums[j] ≤ nums[i]の間、左に移動させます。その後、nums[i]とnums[j]を交換します。- 2つのインデックスを互いに向かって移動させながら、
i + 1から末尾までの部分を反転します。 numsを返します。
def nextPermutation(nums):
n = len(nums)
# 1. the pivot is the last index whose value is smaller than the next one
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# 2. swap it with the rightmost value that is larger than it
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# 3. the suffix after the pivot is falling: reverse it to make it rising
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
落とし穴と境界ケース
- ピボットの探索で
>を≥の代わりに使うこと。[3, 2, 2, 1]では2, 2の組は上昇ではなく、そこで探索を止めると、増加させられないピボットを選んでしまいます。 - ピボットと等しい値と入れ替えること。
[1, 5, 1]では 2 つの 1 を入れ替えても何も変わりません。厳密に大きい値を探してください。 - 末尾部分の最大値と入れ替えること。
[2, 5, 4, 1]では 5 が先頭に来て、4 で始まるすべての並べ替えを飛ばしてしまいます。 - ピボットがない場合を見落とすこと。最大の並べ替えは、配列全体を逆順にして、ソート済みの状態に戻す必要があります。
- Rust では、
n-2から始まるusizeインデックスはn = 1のときパニックになり、ピボットがない場合に 0 を越えて左へ進むとパニックになります。符号付きインデックスを使うか、1 から数えてください。
よくある質問3
Next Permutation の時間計算量は何ですか？
O(n)。右から1回走査してピボットを見つけ、2回目の走査で入れ替える値を見つけ、最後に1回反転させてサフィックスを整えます。すべて配列内で処理するため、追加メモリは O(1) です。
なぜ接尾辞を並べ替えるのではなく、逆順にするのですか？
交換後も接尾辞は降順のままなので、それを反転すれば昇順に並べ替えられます。反転にはO(n)かかりますが、ソートでも同じ結果を得るにはO(n log n)かかります。
Next Permutationは重複する値でも動作しますか？
はい、両方の比較で等しい値をより大きくないものとして扱う限り、そうです。ピボットの検索では ≥ を使って等しい隣接要素をスキップし、交換位置の検索では ≤ を使ってピボットと等しい値をスキップします。すると [1, 5, 1] は、次の異なる並びである [5, 1, 1] になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def nextPermutation(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [2, 5, 4, 1]
期待される出力
[4, 1, 2, 5]