58. Next Permutation

読了目安約2分

その他 / LeetCode 31 (Medium) — 配列を辞書順で次の順列に書き換える

この章の目次

問題

LeetCode 31. Next Permutation（Medium / カテゴリ: その他）

整数の配列 nums を、辞書順でちょうど 1 つ次の順列に並べ替える問題です。 [1, 2, 3] の次は [1, 3, 2] です。 [3, 2, 1] のように辞書順で最大なら、最小の [1, 2, 3] に戻します。

シグネチャは func nextPermutation(_ nums: inout [Int]) で、追加の配列を使わずに nums を直接書き換えます。

考え方

ヒント 1

末尾から見て降順が続いている区間は、並べ替えてもそれ以上大きくできません。初めて nums[i] < nums[i + 1] となる位置 i が、書き換わる場所です。

ヒント 2

手順は 3 歩です。 (1) 末尾から探して nums[i] < nums[i + 1] となる最初の i を見つける。 (2) 末尾から探して nums[i] より大きい最初の要素と nums[i] を交換する。 (3) i + 1 以降を反転して昇順にする。 i が見つからない (全体が降順) ときは、全体を反転するだけです。

Swift 実装のポイント

inout 引数への変更はそのまま呼び出し元の配列に反映されるので、戻り値はありません。
交換は nums.swapAt(i, j)、末尾側の反転は nums[(i + 1)...].reverse() と書けます。スライスへの reverse() は元の配列のその範囲を直接反転します。
見つからないケースを i == -1 のまま進めると、(3) の反転がそのまま全体の反転になり、場合分けが減ります。

模範解答

Swift
class Solution {
    func nextPermutation(_ nums: inout [Int]) {
        var i = nums.count - 2
        while i >= 0 && nums[i] >= nums[i + 1] {
            i -= 1
        }
        if i >= 0 {
            var j = nums.count - 1
            while nums[j] <= nums[i] {
                j -= 1
            }
            nums.swapAt(i, j)
        }
        nums[(i + 1)...].reverse()
    }
}

計算量: O(n)。