Java O(n) Runtime Solution with Explanation of Steps


  • 0
    X

    Finding the next permutation is to find the least possibly increased number which is constructed from the array. [1,2,3,4] constructs 1234. To increase least possibly, convert 34 to 43, namely 1243.
    Step1: write support functions swap which swap two members in an array and reverse function which reverse the subarray[input, array[len-1]]
    Step2: Find next greater permutation. To make the number one step greater, find the first (from right to left) number that is smaller than its successor, call it 'replacee'. To slightly(least possible) increase the number whose digits are the elements of the array, find the the smallest number which is larger than the replacee. Name it replacer. Swap replacee and replacer to increase the whole number least possibly. Now we increased the significant digit lease possibly while kept the less significant part in a increasing order, now reverse the less significant part. The final number we got is the least possibly increased permutation number from the input.

    public class Solution {
    public void nextPermutation(int[] nums) {
        for(int i = nums.length-2 , j = 0; i >= 0; i--){
            if(nums[i] < nums[i+1]){
                for(j = nums.length-1; j > i; j--){
                    if(nums[j]>nums[i]) break;
                }
                swap(nums,i,j);
                reverse(nums,i+1);
                return;
            }
        }
        reverse(nums,0);
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    //reverse from start to end
    public void reverse(int[] nums, int start){
        for( int i = start; i < (nums.length+start)/2;i++){
            swap(nums,i,start+nums.length-1-i);
        }
    }
    

    }


Log in to reply
 

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