Accepted Java solution


  • 1
    M
    public void nextPermutation(int[] nums) {
        if( nums.length <= 1 ) return;
        //find the longest non-increasing suffix
        int length = nums.length;
        int i;
        for(i = length - 2; i>=0; i--){
            if( nums[i+1] > nums[i] ){
                break;
            }
            if( i == 0 ){
                //encounter the largest permutation
                reverseArray(nums, 0, length-1);
                return;
            }
        }
        int pivot = i;
        
        //switch pivot with the smallest number which is greater than pivot (the rightmost one) in suffix
        for( i = pivot + 1; i < length; i++ ){
            if( nums[i] <= nums[pivot] ){
                break;
            }
        }
        int switchIndex = i - 1;
        
        //switch nums[switchIndex] with nums[pivot]
        int tmp = nums[pivot];
        nums[pivot] = nums[switchIndex];
        nums[switchIndex] = tmp;
        //reverse the suffix: index from pivot + 1  to length - 1
        int begin = pivot + 1;
        int end = length - 1;
        reverseArray(nums, begin, end);
    }
    
    public void reverseArray(int[] nums, int begin, int end){
         int tmp;
         while(begin < end){
            tmp = nums[end];
            nums[end] = nums[begin];
            nums[begin] = tmp;
            begin++;
            end--;
        }
    }

Log in to reply
 

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