Description:
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
Solutions:
Approach 1: Optimized solution with time complexity of O(n)
我們首先必須明白“next permutation”的含義是什么钻注。題目中的例子給了我們提示信息，例如對于數(shù)組[1, 2, 3]來說配猫，它的一個全排列是
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
故對于排列2, 1, 3幅恋， 它的下一個排列便是2, 3, 1，再下一個排列便是3, 1, 2泵肄。如果當(dāng)前排列已經(jīng)是全排列的最后一種如3, 2, 1捆交，則下一個排列應(yīng)該是正序排列， 即1, 2, 3腐巢。
但是對于有相同數(shù)字的數(shù)組品追，例如[1, 1, 1, 1, 5]來說，它的全排列為
1, 1, 1, 1, 5
1, 1, 1, 5, 1
1, 1, 5, 1, 1
1, 5, 1, 1, 1
5, 1, 1, 1, 1
通過觀察上述排列冯丙，我們發(fā)現(xiàn)肉瓦，如果把其中的逗號去除，把它們看成數(shù)字胃惜，則第n個排列組成的數(shù)比第n-1的要大泞莉，比n+1的要小。
因此船殉，求下一個排列鲫趁，即求由比這個數(shù)大的下一個排列。
有了這個思路捺弦，我們的算法可如下設(shè)計：
- 從左向右遍歷數(shù)組饮寞，直到找到正序的兩個數(shù)
nums[i-1], nums[i]使得num[i-1] < nums[i]，此時我們可保證nums[i...n-1]是逆序的列吼。 - 在
nums[i...n-1]中幽崩，從左向右遍歷數(shù)組，找到比num[i-1]大的第一個數(shù)nums[j]使得nums[j] > nums[i]寞钥，該數(shù)即是nums[i...n-1]中比nums[i-1]大的最小的數(shù)慌申。 - 由于我們要找到比當(dāng)前排列大的下一個組合，且
nums[i...n-1]是逆序的理郑。故nums[i...n-1]該子序列已經(jīng)是最大值蹄溉，要讓整個組合更大，需更換nums[i-1]您炉。故交換nums[i-1]和nums[j]柒爵。 - 逆序排列
nums[i...n-1]，使得該子序列最小赚爵，這保證了新的排列是所以比題目給定排列大的排列的最小排列棉胀。
但是我們需要注意一下幾點：
- 第1步中的條件必須是
num[i-1] < nums[i]而不能相等，因為如果兩數(shù)相等冀膝，可能會導(dǎo)致求得的下一個排列不變唁奢。例如1, 1, 1, 5, 5的下一個排列本應(yīng)該是1, 1, 5, 1, 5，但如果有相等的條件窝剖，會導(dǎo)致nums[i-1] = nums[i] = 5麻掸。而在nums[i]右已沒有更多的數(shù)，則求得的新排列不變赐纱。 - 第2步中的條件必須是
nums[j] > nums[i-1]而不能相等脊奋。因為我們最終要交換nums[j]和nums[i-1]，若二者相等疙描，則交換后無法得到更大的排列狂魔。
代碼如下：
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
int i = len-1;
for (; i > 0; i--) {
if (nums[i] >= nums[i-1]) break;
}
if (i == 0) {
reverse(nums, 0, len-1);
return;
}
int j = len-1;
for (; j >= i; j--) {
if (nums[j] > nums[i-1]) break;
}
swap(nums, i-1, j);
reverse(nums, i, len-1);
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public void reverse(int[] nums, int start, int end) {
for(int i = start; i <= (start+end)/2; i++) {
swap(nums, i, start+end-i);
}
}
}
- 時間復(fù)雜度分析：
最開始尋找nums[i]和nums[i-1]的復(fù)雜度是O(n)，尋找nums[j]的復(fù)雜度是O(n)淫痰，swap()函數(shù)的復(fù)雜度是O(1)最楷，最后reverse()函數(shù)的復(fù)雜度是O(n)。故最終的時間復(fù)雜度是O(n)待错。
