[brainstorm]
1 find increase pair, swap the pair.
the left number should be as close to the right boundary as possible.
e.g.
2 3
2 0 0 3
2 5 4 3
6 8 9 7
2 see more cases by full permutation
e.g.
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
find some exceptional case,
1 3 2 —> 2 1 3
2 3 1 —>3 1 2
use 2 to replace 1, use 1 3 as minimum.
use bigger first num, use minimum permutation for the remaining.
3 another case
3 5 4 2 1 -> 4 5 3 2 1
as requirement, in place, just O(1) space, that means only swap.
we cannot keep remaining in structure, how to get minimum?
3 5 4 2 1 -> 4 1 2 3 5
however, just reverse the remaining do the trick.
[first bug]
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
if(nums[i]<nums[j]){
swap(nums, i, j);
return;
}
}
}
int l = 0;
int r = n-1;
while(l<r){
swap(nums, l, r);
l++;
r--;
}
}
void swap(int[] nums, int i, int j){
//swap
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
[second bug]
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
if(nums[i]<nums[j]){
swap(nums, i, j);
swap(nums, i+1, n-1);
return;
}
}
}
int l = 0;
int r = n-1;
while(l<r){
swap(nums, l, r);
l++;
r--;
}
}
void swap(int[] nums, int i, int j){
//swap
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
[third bug]
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
if(nums[i]<nums[j]){
for(j=i+1;j<n-1;j++){
if(nums[i]<nums[j] && nums[i]>nums[j+1]){
swap(nums, i, j);
rev(nums, i+1, n-1);
return;
}
}
swap(nums, i, n-1);
rev(nums, i+1, n-1);
return;
}
}
}
int l=0;
int r=n-1;
rev(nums, l, r);
}
void rev(int[] nums, int l, int r){
while(l<r){
swap(nums, l, r);
l++;
r--;
}
}
void swap(int[] nums, int i, int j){
//swap
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}