Java Solution with detailed explanation.


  • 0
    public class Solution {
    // start from the tail
    // 1.get the first elemnt that is smaller than the next one;
    // 2.start from the next element from the first index matches step 2, to search the next bigger element;
    // 3.swap the two elements;
    // 4.reverse all the elements after the first index matches step 2;
    // 5.if there's no first index matches step 2, just reverse all the elements.
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        if(n==0||n<2) return; 
        int i=n-1,first=0;  
        while(i>0){
            if(nums[i]>nums[i-1]){
                first=i-1;
                break;
            }
            i--;
        }
        if(i==0) reverse(nums,0,n-1);
        else{
           int j=first+1;
           int nextbig_index=j;
           int nextbig=nums[j];
           j++;
           while(j<n){
               if(nums[j]>nums[first]&&nums[j]<=nextbig){
                   nextbig=nums[j];
                   nextbig_index=j;
               }
               j++;
           }
           swap(nums,first,nextbig_index);
           reverse(nums,first+1,n-1);
        }
    }
    private void reverse(int[] nums,int start,int end){
        while(start<end){     
                swap(nums,start,end);
                start++;
                end--;
            }
       
    }
    private void swap(int[] nums,int left, int right){
        int temp=nums[left];
        nums[left]=nums[right];
        nums[right]=temp;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.