### 题目

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


### 单纯数学规律 $O(n)$

[9, 8, 3, 7, 5, 9, 9, 9, 8, 7, 0]为例，找到下一个排列法，需要3步：

toSwitch = 4. (数字5所在位置)
[9, 8, 3, 7, >5<, 9, 9, 9, 8, 7, 0]


anotherToSwitch = 9. (第二个7所在位置)
[9, 8, 3, 7, >5<, 9, 9, 9, 8, >7<, 0]


[9, 8, 3, 7, >7<, 9, 9, 9, 8, >5<, 0]


[9, 8, 3, 7, >7<, 0, 5, 8, 9, 9, 9]


[5,4,3,2,1]

[1,2,3,4,5]


#### 代码

public class Solution {
public void nextPermutation(int[] nums) {
// step 1: find 1st number to swap
int toSwap = -1;
for (int i = nums.length-1; i > 0; i--) {
if (nums[i] > nums[i-1]) { toSwap = i-1; break; }
}
// step 2: find 2nd number to swap. And swap them
if (toSwap >= 0){
int anotherToSwap = 0;
for (int i = nums.length-1; i > toSwap ; i--) {
if (nums[i] > nums[toSwap]) { anotherToSwap = i; break; }
}
swap(nums,toSwap,anotherToSwap);
}
// step 3: reverse sort the remainder
reverseSort(nums, toSwap+1, nums.length-1);
}
public void swap(int[] nums, int high, int low) {
int temp = nums[high];
nums[high] = nums[low];
nums[low] = temp;
}
public void reverseSort(int[] nums, int begin, int end) { // begin & end are both included
while (begin < end) {
swap(nums,begin,end);
begin++; end--;
}
}
}