給定一個(gè)整數(shù)數(shù)組來表示排列萝毛，找出其之后的一個(gè)排列。
注意事項(xiàng)
排列中可能包含重復(fù)的整數(shù)
樣例
給出排列[1,3,2,3]言蛇，其下一個(gè)排列是[1,3,3,2]
給出排列[4,3,2,1]僻他，其下一個(gè)排列是[1,2,3,4]
思路：
和 下一個(gè)排列II 一個(gè)思路一樣，細(xì)節(jié)上的區(qū)別
代碼
- version1
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's next permuation
*/
public void swapItem(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void swapList(int[] nums, int i, int j) {
while (i < j) {
swapItem(nums, i, j);
i ++;
j --;
}
}
public int[] nextPermutation(int[] nums) {
int len = nums.length;
if (len <= 1) {
return nums;
}
int i = len - 1;
// 找到那個(gè)滿足 nums[i] > nums[i - 1] 的 i腊尚，i - 1 是需要交換的位置
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
swapList(nums, i, len - 1);
// 找到那個(gè)比 nums[i - 1] 大的數(shù)中最接近 nums[i - 1] 的數(shù)
if (i != 0) {
int j = i;
while (nums[j] <= nums[i - 1]) {
j++;
}
swapItem(nums, j, i-1);
}
return nums;
}
}
- version 2
public class Solution {
/**
* @param num: an array of integers
* @return: return nothing (void), do not return anything, modify num in-place instead
*/
public void reverse(int[] num, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
public int[] nextPermutation(int[] num) {
// find the last increase index
int index = -1;
// 注意此處 i 別越界
for (int i = num.length - 2; i >= 0; i--) {
if (num[i] < num[i + 1]) {
index = i;
break;
}
}
if (index == -1) {
reverse(num, 0, num.length - 1);
return num;
}
// find the first bigger one
int biggerIndex = index + 1;
// 尋找 biggerIndex 的順序很重要吨拗，從右往左開始是依次遞增的順序
for (int i = num.length - 1; i > index; i--) {
if (num[i] > num[index]) {
biggerIndex = i;
break;
}
}
// swap them to make the permutation bigger
int temp = num[index];
num[index] = num[biggerIndex];
num[biggerIndex] = temp;
// reverse the last part
reverse(num, index + 1, num.length - 1);
return num;
}
}
細(xì)節(jié)上需要注意的是尋找 index 和 biggerIndex 的兩個(gè)for循環(huán)不能忘記加break
