原题链接：
31. Next Permutation
31. Next Permutation
【思路】
首先，我们来了解一下——字典序法：
C++的STL库里面有
nextPermutation()方法，其实现就是字典序法。
下图简单明了地介绍了字典序法
例如，1234的全排列如下：
简单归纳，从右边开始，找到第一个正序数 nums[i] ，然后从右边找第一个大于 num[i] 的数 nums[j]（j > i），找到之后交换 nums[i] 和 nums[j] ，最后将 nums[i + 1] 至 nums[nums.length – 1]之间的数进行反转：
public void nextPermutation(int[] nums) {
for (int i = nums.length - 2; i >= 0; i--)
if (nums[i] < nums[i + 1])
for (int j = nums.length - 1; j > i; j--)
if (nums[i] < nums[j]) {
swap(nums, i, j);
reverse(nums, i + 1, nums.length - 1);
return;
}
reverse(nums, 0, nums.length - 1);
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
private void reverse(int[] nums, int left, int right) {
while (left < right)
swap(nums, left++, right--);
}
265 / 265
test cases passed.
Runtime:
2 ms
Your runtime beats 9.15% of javasubmissions.
欢迎优化！
版权声明：本文为happyaaaaaaaaaaa原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。