Difficulty: medium
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
這道題的思路一旦理解了還是非常簡單清楚的粥脚。舉幾個例子：
1 3 5 2 4 3
1 3 5 3 2 4
比如上面的例子中谤碳，從右往左數(shù)前兩位3 4 是遞增的忽冻，也就是最大的排列；但到了第三位2 出現(xiàn)了第一次左邊的數(shù)字比右邊的數(shù)字大的情況，而2所在的index就是我們需要找到的first. 然后我們在[first + 1, n - 1]中繼續(xù)找比2大的最小的數(shù)轻猖，這里是3鲜结，也就是nums[k], 然后我們交換nums[first]和nums[k]. 上面例子就會變成1 3 5 3 2 4. 因為我們是要取下一個排列，也就是比之前排列大的最小的排列您访，所以我們要排序[nums[k + 1], nums[n- 1]], 這里恰好2 4 已經(jīng)排好序了铅忿。
1 4 5 3 3 6 5
1 4 5 3 5 3 6
4 3 2 1
1 2 3 4
像 4 3 2 1這種已經(jīng)是最高排列的，就返回正序排列灵汪。
注意一下檀训，一開始交換數(shù)組里的兩個元素的swap方法寫錯了，寫成了：
private void swap(int a, int b){
int temp = a;
a = b;
b = temp;
}
但是這里傳入?yún)?shù)是基本類型享言，a峻凫，b傳的是值，修改ab對外面的nums[i],nums[j]無影響览露，所以要修改數(shù)組元素必須在方法參數(shù)里寫上
swap(int[] nums, int a, int b)
class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0 || nums.length == 1){
return;
}
int n = nums.length;
int first = -1;
for (int j = n - 1; j > 0; j--){
if (nums[j - 1] < nums[j]){
first = j - 1;
break;
}
}
if (first == -1){
Arrays.sort(nums);
return;
}
int minNext = Integer.MAX_VALUE;
int minIndex = -1;
for (int k = first + 1; k < n; k++){
if (nums[k] > nums[first]){
if (nums[k] < minNext){
minNext = nums[k];
minIndex = k;
}
}
}
swap(nums, first, minIndex);
Arrays.sort(nums, first + 1, n);
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
