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
算法分析
算法
如图所示，算法分为如下几个步骤：
- 从数列的最后一位开始，寻找遇到的第一个非升序的值，索引记为i，如（3298765中从后向前第一个非升序的值为2）。
- 从数列的最后一位向前寻找第一个比步骤一中大的数，交换两个数的位置。
- 将数列中i之后的数按从小到大的顺序排列，即可得到比原始序列稍大的一个数列。
代码
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i+1]) {//从数组后向前找出第一个非降序的值
i --;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {//从数组后向前找出第一个比nums[i]大的值
j --;
}
swap(nums, i, j);//交换i和j的位置
}
reverse(nums, i + 1);//由于要寻找下一个大一点的数组,因此将数组从索引i+1开始的值按从小到大的顺序排列
}
private void reverse(int[] nums, int start) {//反转数列
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) {//交换数组中两个数的位置
int temp;
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
