LeetCode 解答 #31. Next Permutation プログラミング練習

問題：

難易度:　medium
入力:　int型array
目的: 入力されたarrayの数字を操作し次に多きい数字になるように順番を組み直せ
出力:　なし

出力はなしですがちゃんと入力Arrayをテストで見ています。
少し解りにくい問題ですが、要するに
入力が[1,3,2]の場合、
入力された数字1,2,3を組み合わせ、132の次に大きい組み合わせに変えればいいのです。
なので答えは[2,1,3]になります。
入力が[3,2,1]だった場合、
321より大きい組み合わせが存在しない為、一番小さい組み合わせの[1,2,3]に直します。

注意すべき事:　

• メモリはO(1)に抑える

• 入力が一番大きい組み合わせの場合一番小さい組み合わせにする。

以下回答です。

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length < 2) return;
        int i=nums.length - 2;
        for (; i>= 0; i--) {
            if (nums[i] < nums[i+1]) break;
        }
        int j = nums.length - 1;
        if (i >= 0) {
            while (j>0 && nums[j] <= nums[i]) j--;
            swap(nums, i, j);   
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public void reverse(int[] nums, int i, int j) {
        while(i < j) swap(nums, i++, j--);
    }
}

まずiで、後ろからどこまで降順なのかを調べます。
もし完全に降順だった場合、一番大きい組み合わせなので、
ifを飛び越えてすべての数字をスワップし、一番小さい組み合わせになります。
完全な降順じゃない場合、jを使い後ろから一番iが指す数字より大きい数字を探します。
それをスワップし、iから後ろの数字を降順に組み合わせ直せば答えになります。

今日は以上。
よいプログラミング生活を！