31. 下一个排列
自己解法
这个题的思路就是从后往前，找到不是升序排列的节点，然后去找已遍历过的元素中，第一个比这个节点大的，两者进行交换。交换完之后，再对后半段元素进行反转排序，这个自己写的时候忘记了。如果本身元素从头到尾就是降序排列的，就直接反转，取最小排列。时间复杂度为O(n),空间复杂度为O（1），没使用额外的空间。
class Solution {
public void nextPermutation(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return;
}
for (int i = nums.length - 1; i > 0; i--) {
// 找到不是降序的切入点
if (nums[i] > nums[i - 1]) {
int left = i - 1;
int right = nums.length - 1;
for (int j = nums.length - 1; j >= i; j--) {
if (nums[j] > nums[left]) {
right = j;
break;
}
}
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
// left后面的内容要进行反转才是最小
reverse(nums, ++left, nums.length - 1);
return;
}
}
// 上面一直没处理的话，说明数组内原本都是降序的，进行全反转
reverse(nums, 0, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
官方解法
思路一致，但写法更简洁，找出不是降序排序的节点，直接找出就好，不用在循环里处理后续的逻辑，最后这个反转，直接用i + 1,包括了交换后反转交换节点后面的逻辑，以及未交换时，反转整个数组的逻辑。
public class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
