public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
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 temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
We iterate through nums
from right to left to find the number nums[i]
where the descending order occurs for the first time. Then we scan through the nums from right to i+1
to find a number that is greater nums[i]
and swap the number with it. Finally, we reverse nums[i+1] ... nums[nums.length-1]
.
By doing so, we can guarantee that:
- The next permutation is always greater or equal to the current permutation (we assume the numbers in the current permutation are not sorted in descending order).
- There does not exist a permutation that is greater than the current permutation and smaller than the next permutation generated by the above code.
- If the numbers in the current permutation are already sorted in descending order (i.e. greatest possible value), the next permutation has the smallest value.
Time Complexity: O(n)
Extra Space: O(1)
Top comments (0)