Open Shawngbk opened 7 years ago
http://blog.csdn.net/u012848330/article/details/52090111 https://yq.aliyun.com/articles/863 http://www.cnblogs.com/springfor/p/3896245.html 从后往前遍历数组，如果一直是逐渐增大的，则已经是最大的了，如果出现了一个下降的数，那么遍历就到此为止，因为这已遍历的部分就可以排列成下一个较大的数了 当找到这个突然下降的点A后，由于它后面已经排列为“最大”，即从前往后一直变小，所以应该从后面比A大的数中找最小的点B，然后A和B交换位置。这个时候以B开头，后面也是最大的排列，由于需要找下一个较大的数，应该把B后面的排列改为最小的，只需要将后面的数组顺序逆转一下即可。如果一直没有找到下降的点，则全部逆转即可。
public class Solution { public void nextPermutation(int[] nums) { int len = nums.length; int i = 0; for(i = len-1; i > 0; i--) { if(nums[i] <= nums[i-1]) { continue; } else { for(int j = len-1; j >= i; j--) { if(nums[j] <= nums[i-1]) { continue; } else { int temp = nums[i-1]; nums[i-1] = nums[j]; nums[j] = temp; } break; } break; } } swaphelper(nums, i, len-1); } private void swaphelper(int[] nums, int left, int right) { int temp = 0; while(left < right) { temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } }
google
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
http://blog.csdn.net/u012848330/article/details/52090111 https://yq.aliyun.com/articles/863 http://www.cnblogs.com/springfor/p/3896245.html 从后往前遍历数组，如果一直是逐渐增大的，则已经是最大的了，如果出现了一个下降的数，那么遍历就到此为止，因为这已遍历的部分就可以排列成下一个较大的数了 当找到这个突然下降的点A后，由于它后面已经排列为“最大”，即从前往后一直变小，所以应该从后面比A大的数中找最小的点B，然后A和B交换位置。这个时候以B开头，后面也是最大的排列，由于需要找下一个较大的数，应该把B后面的排列改为最小的，只需要将后面的数组顺序逆转一下即可。如果一直没有找到下降的点，则全部逆转即可。
public class Solution { public void nextPermutation(int[] nums) { int len = nums.length; int i = 0; for(i = len-1; i > 0; i--) { if(nums[i] <= nums[i-1]) { continue; } else { for(int j = len-1; j >= i; j--) { if(nums[j] <= nums[i-1]) { continue; } else { int temp = nums[i-1]; nums[i-1] = nums[j]; nums[j] = temp; } break; } break; } } swaphelper(nums, i, len-1); } private void swaphelper(int[] nums, int left, int right) { int temp = 0; while(left < right) { temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } }