31. Next Permutation
Tags: ‘Array’
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
Solution
如果每一个digit 都大于下一个digit e.g. $9876543$ 他就是最大的permutation.
如果有任何一个digit x 小于下一个digit，e.g.$9837654$, 我们要发现他之后rightmost近并且大于他的digit，并且交换.
然后Reverse after x.
$O(n) O(1)$
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0) return;
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i+1]) {
i--;
}
if (i >= 0) { // if not entirely descending(no larger permutation)
int j = nums.length - 1;
while(nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i+1, nums.length - 1);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
}