Next Permutation

Question:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法代碼

import java.util.Arrays;

public class LeetCode31 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{3, 2, 1};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{1, 1, 5};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{5, 3, 4, 2, 1};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{1, 3, 2};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{4, 2, 0, 2, 3, 2, 0};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{2, 2, 3, 4, 2, 3, 1, 1, 2};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
        nums = new int[]{1, 1};
        System.out.print("Array string : " + Arrays.toString(nums));
        new LeetCode31().nextPermutation(nums);
        System.out.println(",nextPermutation: " + Arrays.toString(nums));
    }
    
    public void nextPermutation(int[] nums) {
        // 空數(shù)組和只有一個(gè)元素的數(shù)組，直接返回
        if(nums == null || nums.length < 2) {
            return;
        }
        int i = nums.length - 2;
        // 從后往前找，數(shù)據(jù)增大則跳過，如果發(fā)現(xiàn)數(shù)據(jù)變小，則說明找到了更大的排列
        while(i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // If such arrangement is not possible, 
        // it must rearrange it as the lowest possible order
        // 沒有找到解，元素全部反轉(zhuǎn)
        if(i == -1) {
            reverse(nums, 0);
            return;
        }
        int j = i + 1;
        // 因?yàn)閕后面的元素是有序的，利用反轉(zhuǎn)對(duì)i后面的元素進(jìn)行排序
        reverse(nums, j);
        // 找到數(shù)據(jù)交換的位置
        while(nums[j] <= nums[i]) {
            j++;
        }
        swap(nums, i, j);
    }
    
    private void reverse(int[] nums , int start) {
        int i = start;
        int j = nums.length - 1;
        while(i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Output：

Array string : [1, 2, 3],nextPermutation: [1, 3, 2]
Array string : [3, 2, 1],nextPermutation: [1, 2, 3]
Array string : [1, 1, 5],nextPermutation: [1, 5, 1]
Array string : [5, 3, 4, 2, 1],nextPermutation: [5, 4, 1, 2, 3]
Array string : [1, 3, 2],nextPermutation: [2, 1, 3]
Array string : [4, 2, 0, 2, 3, 2, 0],nextPermutation: [4, 2, 0, 3, 0, 2, 2]
Array string : [2, 2, 3, 4, 2, 3, 1, 1, 2],nextPermutation: [2, 2, 3, 4, 2, 3, 1, 2, 1]
Array string : [1, 1],nextPermutation: [1, 1]

Time And Space Complexity

Time: 在最壞的情況下，只需要對(duì)整個(gè)數(shù)組進(jìn)行兩次掃描
Space: 不需要使用額外的存儲(chǔ)空間，原地替換

Tips

關(guān)鍵點(diǎn)：

• 從后往前遍歷元素，如果元素是增大或者相等的則跳過，如果出現(xiàn)一個(gè)變小的元素則說明，這個(gè)就是解的位置，假定為index，如下圖（圖中index的值為i-1）：

  
  

• 如果全部元素遍歷完，都是遞增或者是相等的，則說明沒有更小排列，反轉(zhuǎn)數(shù)組，直接返回

• 對(duì)數(shù)組index后的元素進(jìn)行遞增排序，即對(duì)原數(shù)組index后的元素做反轉(zhuǎn)

• 在index后尋找第一個(gè)大于第index處的元素，與index位置的元素交換

求解過程可以參考下圖，下圖中第三步與第四步交換了次序：

/**
  *  一開始，不太優(yōu)雅的實(shí)現(xiàn)代碼，供反思
  */
public void nextPermutation(int[] nums) {
        // 空數(shù)組和只有一個(gè)元素的數(shù)組，直接返回
        if(nums == null || nums.length < 2) {
            return;
        }
        // 用于標(biāo)記是否只需要重新排序即可
        boolean flag = false;
        // 數(shù)據(jù)交換點(diǎn)
        int index = nums.length - 1;
        // 從后往前找，數(shù)據(jù)增大則跳過，如果發(fā)現(xiàn)數(shù)據(jù)變小，則說明找到了更大的排列
        for(int i = index - 1; i >= 0; i--) {
            if(nums[i] > nums[i + 1]) {
                if(i == 0) {
                    flag = true;
                }
            }
            // 找到更大的排列
            if(nums[i] < nums[i + 1]){
                index = i;
                break;
            }
        }
        if(flag) {
            //If such arrangement is not possible, 
            //it must rearrange it as the lowest possible order
            Arrays.sort(nums);
            return;
        }
        if(nums.length - index > 1) {
            Arrays.sort(nums, index + 1, nums.length);
        }
        for(int j = index + 1; j < nums.length; j++) {
            if(nums[j] > nums[index]) {
                int tmp = nums[index];
                nums[index] = nums[j];
                nums[j] = tmp;
                break;
            }
        }
        
    }