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, do not allocate 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

算法分析

算法

如圖所示，算法分為如下幾個(gè)步驟：

1. 從數(shù)列的最后一位開(kāi)始，尋找遇到的第一個(gè)非升序的值，索引記為i，如（3298765中從后向前第一個(gè)非升序的值為2）。
2. 從數(shù)列的最后一位向前尋找第一個(gè)比步驟一中大的數(shù)，交換兩個(gè)數(shù)的位置。
3. 將數(shù)列中i之后的數(shù)按從小到大的順序排列，即可得到比原始序列稍大的一個(gè)數(shù)列。

代碼

public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) {//從數(shù)組后向前找出第一個(gè)非降序的值
            i --;
        }

        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {//從數(shù)組后向前找出第一個(gè)比nums[i]大的值
                j --;
            }
            swap(nums, i, j);//交換i和j的位置
        }
        reverse(nums, i + 1);//由于要尋找下一個(gè)大一點(diǎn)的數(shù)組,因此將數(shù)組從索引i+1開(kāi)始的值按從小到大的順序排列
    }
    private void reverse(int[] nums, int start) {//反轉(zhuǎn)數(shù)列
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i ++;
            j --;
        }
    }

    private void swap(int[] nums, int i, int j) {//交換數(shù)組中兩個(gè)數(shù)的位置
        int temp;
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

參考

LeetCode