LeetCode解説　一日一問　31.Next Permutation

LeetCodeって？
問題
回答
コード
結果

LeetCodeって？

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

Pythonではじめるアルゴリズム入門伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井敏克 ]

問題

Next Permutation - LeetCode

Can you solve this real interview question? Next Permutation - A permutation of an array of integers is an arrangement of its members into a sequence or linear ...

タイトル：31. Next Permutation

難易度：Medium

内容：

０以上の整数の入ったリスト nums が与えられる。
nums を整数に見立てる。例：[1, 2, 3]　→　123
nums を構成する値を使って、上の整数の次に大きい整数を作る。例：123　→　132
これ以上大きい整数が作れない場合、最小の整数を作る。例：321　→　123

例：

Input: nums = [1,2,3]
Output: [1,3,2]

Input: nums = [3,2,1]
Output: [1,2,3]

Input: nums = [1,1,5]
Output: [1,5,1]

この問題は Output の値を返すのではなく、nums の中身を修正することで回答とします。

回答

nums = [1, 2, 5, 4, 3] を例として考えてみます。

この場合の回答は[1, 3, 2 ,4, 5] になります。2要素目の２が３に繰り上がっています。

なぜ２要素目が繰り上がるかというと、３から５要素目は降順になっており、３から５要素目のいずれかを入れ替えてもこれ以上大きくしようがないためです。

したがって２要素目の２が、３から５要素目の中で一番小さな３になり、３から５要素目を残りの値で昇順にしたものが、[1, 2, 5, 4, 3] の次の値となるわけです。

具体的には以下の手順になります。

１．４要素目を i 、５要素目を j として比較、i > j と降順なのでスルー

２．i を３要素に移動、i > j と降順なのでスルー

３．j を４要素に移動、i > j と降順なのでスルー

４．i を２要素に移動、i ＞ j となるので i と j を入れ替え

５．３から５要素目をソート

コード

上記の理論を一般化してコードにします。

class Solution(object):                
    def nextPermutation(self, nums):    
        for i in range(len(nums) - 1):
            for j in range(i + 1):
                if nums[- j - 1] > nums[- i - 2]:
                    tmp = nums[- i - 2]
                    nums[- i - 2] = nums[- j - 1]
                    nums[- j - 1] = tmp
                    nums[:] = nums[:len(nums) - i - 1] + sorted(nums[len(nums) - i - 1:])
                    return
        nums.sort()
        return

コードはgithubにも保管しています。