Next Permutation
Question:
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 and use only constant 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
解法代碼
import java.util.Arrays;
public class LeetCode31 {
public static void main(String[] args) {
int[] nums = new int[]{1, 2, 3};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{3, 2, 1};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{1, 1, 5};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{5, 3, 4, 2, 1};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{1, 3, 2};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{4, 2, 0, 2, 3, 2, 0};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{2, 2, 3, 4, 2, 3, 1, 1, 2};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
nums = new int[]{1, 1};
System.out.print("Array string : " + Arrays.toString(nums));
new LeetCode31().nextPermutation(nums);
System.out.println(",nextPermutation: " + Arrays.toString(nums));
}
public void nextPermutation(int[] nums) {
// 空數(shù)組和只有一個元素的數(shù)組宏邮，直接返回
if(nums == null || nums.length < 2) {
return;
}
int i = nums.length - 2;
// 從后往前找侍匙，數(shù)據(jù)增大則跳過伏恐，如果發(fā)現(xiàn)數(shù)據(jù)變小米苹，則說明找到了更大的排列
while(i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If such arrangement is not possible,
// it must rearrange it as the lowest possible order
// 沒有找到解，元素全部反轉(zhuǎn)
if(i == -1) {
reverse(nums, 0);
return;
}
int j = i + 1;
// 因為i后面的元素是有序的，利用反轉(zhuǎn)對i后面的元素進行排序
reverse(nums, j);
// 找到數(shù)據(jù)交換的位置
while(nums[j] <= nums[i]) {
j++;
}
swap(nums, i, j);
}
private void reverse(int[] nums , int start) {
int i = start;
int j = nums.length - 1;
while(i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
Output：
Array string : [1, 2, 3],nextPermutation: [1, 3, 2]
Array string : [3, 2, 1],nextPermutation: [1, 2, 3]
Array string : [1, 1, 5],nextPermutation: [1, 5, 1]
Array string : [5, 3, 4, 2, 1],nextPermutation: [5, 4, 1, 2, 3]
Array string : [1, 3, 2],nextPermutation: [2, 1, 3]
Array string : [4, 2, 0, 2, 3, 2, 0],nextPermutation: [4, 2, 0, 3, 0, 2, 2]
Array string : [2, 2, 3, 4, 2, 3, 1, 1, 2],nextPermutation: [2, 2, 3, 4, 2, 3, 1, 2, 1]
Array string : [1, 1],nextPermutation: [1, 1]
Time And Space Complexity
Time:
在最壞的情況下，只需要對整個數(shù)組進行兩次掃描
Space:不需要使用額外的存儲空間薄湿，原地替換
Tips
關(guān)鍵點：
-
從后往前遍歷元素，如果元素是增大或者相等的則跳過偷卧，如果出現(xiàn)一個變小的元素則說明豺瘤，這個就是解的位置，假定為index涯冠，如下圖（圖中index的值為i-1）：
如果全部元素遍歷完炉奴，都是遞增或者是相等的，則說明沒有更小排列蛇更，反轉(zhuǎn)數(shù)組瞻赶，直接返回
對數(shù)組index后的元素進行遞增排序，即對原數(shù)組index后的元素做反轉(zhuǎn)
在index后尋找第一個大于第index處的元素派任，與index位置的元素交換
求解過程可以參考下圖砸逊，下圖中第三步與第四步交換了次序：
/**
* 一開始耍群，不太優(yōu)雅的實現(xiàn)代碼罢绽，供反思
*/
public void nextPermutation(int[] nums) {
// 空數(shù)組和只有一個元素的數(shù)組，直接返回
if(nums == null || nums.length < 2) {
return;
}
// 用于標記是否只需要重新排序即可
boolean flag = false;
// 數(shù)據(jù)交換點
int index = nums.length - 1;
// 從后往前找类早，數(shù)據(jù)增大則跳過豆混，如果發(fā)現(xiàn)數(shù)據(jù)變小篓像，則說明找到了更大的排列
for(int i = index - 1; i >= 0; i--) {
if(nums[i] > nums[i + 1]) {
if(i == 0) {
flag = true;
}
}
// 找到更大的排列
if(nums[i] < nums[i + 1]){
index = i;
break;
}
}
if(flag) {
//If such arrangement is not possible,
//it must rearrange it as the lowest possible order
Arrays.sort(nums);
return;
}
if(nums.length - index > 1) {
Arrays.sort(nums, index + 1, nums.length);
}
for(int j = index + 1; j < nums.length; j++) {
if(nums[j] > nums[index]) {
int tmp = nums[index];
nums[index] = nums[j];
nums[j] = tmp;
break;
}
}
}
