31. Next Permutation - Medium

前往題目

想法

• 這題忙了兩三天才回來再研究，沒什麼想法

思路

這題最優解實作不難，但原理難證明，也不想花時間看了

1. 從後往前看遇到不是遞增的數，就是pivot，例如1543，那1就是pivot
2. 如果都是遞增，那就直接reverse就是答案，例如54321，這就是最大的數了，下一個就是重新開始，變成12345
3. 在Pivot之後的數列從後往前找尋第一個比pivot大的數，和他交換位置
4. 最後反轉整個pivot(不包含)之後的陣列就是答案

Code

來自討論區的答案

另外也參考了這支影片，解釋得很清楚

class Solution {
    public void nextPermutation(int[] nums) {
        int ind1=-1;
        int ind2=-1;
        // step 1 find breaking point 
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                ind1=i;
                break;
            }
        }
        // if there is no breaking  point 
        if(ind1==-1){
            reverse(nums,0);
        }
        
        else{
            // step 2 find next greater element and swap with ind2
            for(int i=nums.length-1;i>=0;i--){
                if(nums[i]>nums[ind1]){
                    ind2=i;
                    break;
                }
            }

            swap(nums,ind1,ind2);
            // step 3 reverse the rest right half
            reverse(nums,ind1+1);
        }
    }
    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    void reverse(int[] nums,int start){
        int i=start;
        int j=nums.length-1;
        while(i<j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }
}

2024/04/19

• 毫無頭緒的一題，知道規律就簡單多了