【Leetcode】Next Permutation
来源：程序员人生 发布时间：2016-06-25 15:29:49 阅读次数：2265次
题目链接：https://leetcode.com/problems/next-permutation/
题目：
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, do not allocate 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
思路：
见注释。。。。
算法：
public void nextPermutation(int[] nums) {
int pos = ⑴;
// 找到最后1个升序位置
for (int i = nums.length - 1; i >= 1; i--) {
if (nums[i] > nums[i - 1]) {
pos = i - 1;
break;
}
}
// 如果没有升序 如3 2 1 需要反转为1 2 3
if (pos < 0) {
nums = reverse(nums, 0, nums.length - 1);
return;
}
// 存在升序 找到pos以后最后1个大于pos的位置
// 举例 如1 2 5 4 3 1下1个排列应当是 1 3 1 2 4 5，
// 首先定位pos元素为2；找到元素3；二者交换：1 3 5 4 2 1；将5~1反转；
for (int i = nums.length - 1; i > pos; i--) {
if (nums[i] > nums[pos]) {
int tmp = nums[i];
nums[i] = nums[pos];
nums[pos] = tmp;
break;
}
}
// 将pos以后元素全部反转
nums = reverse(nums, pos + 1, nums.length - 1);
}
public int[] reverse(int nums[], int start, int end) {
while (start < end) {
int tmp = nums[start];
nums[start] = nums[end];
nums[end] = tmp;
start++;
end--;
}
return nums;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
