[LeetCode] 31. Next Permutation

問題の説明

問題を解く

時間複雑度:O(N!)/空間複雑度：O（N）

1. list(수열)에 대해서 list[i-1] < list[i]를 만족하는 가장 큰 수를 찾는다. 
2. 1번에서 찾은 i-1에 대하여 list[i-1] < list[j]를 만족하는 가장 큰 j를 찾는다.
3. list[i-1], list[j]를 swap한다. 
4. list[i ... n-1]을 reverse 시킨다. 

ソースコード（JAVA）

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