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
算法分析
算法
如圖所示悠轩，算法分為如下幾個步驟：
- 從數(shù)列的最后一位開始溢豆，尋找遇到的第一個非升序的值种玛，索引記為i双肤，如（3298765中從后向前第一個非升序的值為2）。
- 從數(shù)列的最后一位向前尋找第一個比步驟一中大的數(shù)业筏，交換兩個數(shù)的位置。
- 將數(shù)列中i之后的數(shù)按從小到大的順序排列，即可得到比原始序列稍大的一個數(shù)列球散。
代碼
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i+1]) {//從數(shù)組后向前找出第一個非降序的值
i --;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {//從數(shù)組后向前找出第一個比nums[i]大的值
j --;
}
swap(nums, i, j);//交換i和j的位置
}
reverse(nums, i + 1);//由于要尋找下一個大一點的數(shù)組,因此將數(shù)組從索引i+1開始的值按從小到大的順序排列
}
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ù)組中兩個數(shù)的位置
int temp;
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
