LeetCodeって？
LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。
2022年12月現在2,000問を超える問題が登録されています。
各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。
正誤判定は自動で行われます。
使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。
私はPython3で解いています。
Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量 [ 増井 敏克 ]
問題
タイトル：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にも保管しています。
結果
コメント