1.题目描述
2.思路
给定一个整数数组 nums,找出它的下一个字典序排列(即比当前排列“刚好大一点”的排列)。
如果不存在下一个排列(即已是最大排列),则返回最小排列(升序排列)。
比如初始数组是[1,2,3],所以对于第一个位置有3种可能,对于第二个位置有2种可能,最后一个位置有1种可能,所以总共有3*2=6种。
从小到大的排序:
【1,2,3】、【1,3,2】、【2,1,3】、【2,3,1】,【3,1,2】,【3,2,1】
但是要求按字典序大小,查找下一个排列的数
思路可以参考全排列
思路2:
(1)找从右往左第一个变大的地方
(2)在后面找一个刚比它大的数交换
(3)然后把后面升序排列(让它变最小)
3.代码实现
class Solution {
public void nextPermutation(int[] nums) {
int i=nums.length-2;
while(i>=0&&nums[i]>=nums[i+1])
{
i--;
}
if(i>=0)
{
int j=nums.length-1;
while(j>=0&&nums[i]>=nums[j])
{
j--;
}
swap(nums,i,j);
}
reverse(nums,i+1);
}
public void swap(int[] nums,int i,int j)
{
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
public void reverse(int[] nums,int start)
{
int left=start;
int right=nums.length-1;
while(left<right)
{
swap(nums,left,right);
left++;
right--;
}
}
}
class Solution {
public void nextPermutation(int[] nums) {
// 示例:[1, 3, 5, 4, 2]
// 下一个排列是:[1, 4, 2, 3, 5]
// 从后往前找第一个下降的位置(即 nums[i] < nums[i+1])
int i = nums.length - 2; // 从倒数第二个位置开始
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--; // 找到第一个 "升序对" 的左边那个数
}
// 如果找到了这样的 i(说明当前排列不是最大的)
if (i >= 0) {
// 从后往前找第一个比 nums[i] 大的元素
int j = nums.length - 1;
while (j >= 0 && nums[i] >= nums[j]) {
j--;
}
// 交换 nums[i] 和 nums[j]
swap(nums, i, j);
}
// 把 i+1 之后的部分反转,使它成为最小的排列(升序)
reverse(nums, i + 1);
}
// 交换数组中下标 i 和 j 的两个元素
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 反转数组中从 start 到末尾的元素(原地升序)
public void reverse(int[] nums, int start) {
int left = start, right = nums.length - 1;
while (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
}