下一个排列

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def nextPermutation(self , nums: List[int]) -> List[int]:
        # write code here
        # 判断是否为下降序列
        is_decrese = True
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                is_decrese = False
        if is_decrese:
            return nums[::-1]

        # 右指针最右边，逐步往左边找比右指针小的值，找到交换返回即可
        # 一次次找，找不到就左移右指针
        right = len(nums)-1
        while right > 0:
            for i in range(right-1, -1,-1):
                if nums[i] < nums[right]:
                    nums[i], nums[right] = nums[right], nums[i]
                    return nums
            right -= 1

        return nums

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # 思考：
        # 1. 对于某个位置i，如果前面保持相同，而位置i的数变大，那么就形成了更大的排列（定义）。
        # 2. 因此，只能从位置i后面的位置取更大的数放到位置i来，就不会影响前面的结果，此时位置i越靠右越好。
        # 因此问题的关键是：需要找到位置i，使得位置i后面存在一个刚好比位置i的数大的数，那我们把这个数放到位置i，就使得前面不变，而将位置i的数稍微变大了；然后将后面再排序一下，使得后面构成最小的排列。
        n = len(nums)
        exist = False # 是否存在后面一个数比位置i的数更大
        for i in range(n-1, -1, -1):
            if max(nums[i:]) > nums[i]:
                exist = True
                break
        if not exist: # 如果不存在，意味着整个数组是递减的，反序输出即可。
            return nums[::-1]
        # 寻找后面刚好比nums[i]稍大的那个数的位置minlargej
        minlargej, minlarge = i, float('inf')
        for j in range(i+1, n):
            diff = nums[j]-nums[i]
            if diff > 0 and diff < minlarge:
                minlarge = diff
                minlargej = j
        nums[i], nums[minlargej] = nums[minlargej], nums[i] # 交换一下，使得nums[i]稍微变大
        nums[i+1:] = sorted(nums[i+1:]) # 排序一下后面的数组，形成最小的排列
        return nums

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型一维数组
*/
func nextPermutation( nums []int ) []int {
    n:=len(nums)
    if n<2{
        return nums
    }
    i,j,k:=n-2,n-1,n-1
    for i>=0&&nums[i]>=nums[j]{
        i--
        j--
    }
    if i>=0{
        for nums[i]>=nums[k]{
            k--
        }
        nums[i],nums[k]=nums[k],nums[i]
    }
    l,r:=j,n-1
    for l<r{
        nums[l],nums[r]=nums[r],nums[l]
        l++
        r--
    }
    return nums
}

package main

import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型一维数组
 */
func nextPermutation(nums []int) []int {
	xLen := len(nums)
	if xLen <= 1 {
		return nums
	}
	idx, minNum := xLen-2, xLen-1
	for ; idx > 0; idx-- {
		if nums[idx] < nums[idx+1] {
			for nums[idx] >= nums[minNum] {
				minNum--
			}
			break
		}
	}
	nums[idx], nums[minNum] = nums[minNum], nums[idx]
	sort.Ints(nums[idx+1:])
	return nums
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> nextPermutation(vector<int>& nums) {
        // write code here
        next_permutation(nums.begin(), nums.end());
        return nums;
        
    }
};

class Solution:
    def nextPermutation(self , nums: List[int]) -> List[int]:
        # write code here
        if len(nums)==1:return nums
        for i in range(len(nums)-1,0,-1):
            if nums[i]>nums[i-1]:
                t = nums[i]
                nums[i] = nums[i-1]
                nums[i-1] = t
                return nums
        return nums[::-1]

class Solution:
    def nextPermutation(self , nums: List[int]) -> List[int]:
        # write code here
        if len(nums) < 2 :
            return nums
        p1 = 0
        p2 = len(nums) - 2
        
        flag = 0
        while p2 >= 0:
            for i in range(p2, len(nums)):
                if nums[i] > nums[p2]:
                    tmp = nums[i]
                    nums[i] = nums[p2]
                    nums[p2] = tmp
                    flag = 1
                    break
            if flag == 1:
                break
            else:
                p2 -= 1
        if flag == 0:
            nums.sort()
        
        return nums

import java.util.*;

public class Solution {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */

    public int[] nextPermutation (int[] nums) {
        int n = nums.length;
        int i = n - 2, j = n - 1;
        while (i >= 0 && nums[i] >= nums[i+1]) -- i;
        if (i >= 0){
            while (j > i && nums[i] >= nums[j]) -- j;
            // 交换数组中这2个位置的值
            getSwap(nums, i ,j);
        }
        // 翻转，从某个位置之后的部分数组
        getReverse(nums, i+1);
        return nums;
    }

    private void getReverse(int[] nums, int i) {
        int left = i, right = nums.length - 1;
        while (left < right){
            getSwap(nums, left ++, right --);
        }
    }

    private void getSwap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    boolean[] mark;
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        mark = new boolean[num.length];
        Arrays.sort(num);
        LinkedList<Integer> path = new LinkedList<Integer>();
        dfs(num,path);
        return res;
    }
    public void dfs(int[] num,LinkedList<Integer> path){
        if(path.size()==num.length){
            if(res.contains(path)) return;
            res.add(new ArrayList(path));
                return;
        }
        for(int i=0;i<num.length;i++){
            if(mark[i]==true)
                continue;
            path.add(num[i]);
            mark[i]=true;
            dfs(num,path);
            path.remove(path.size()-1);
            mark[i]=false;
        }
    }
    public int[] nextPermutation (int[] nums) {
        if(nums.length==1) return new int[]{nums[0]};
        int[] cur=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            cur[i]=nums[i];
        }
        ArrayList<ArrayList<Integer>> res = permuteUnique(cur);
        int mark=0;int n=res.get(0).size();
        for(int i=0;i<res.size();i++){
            ArrayList a=res.get(i);
            for(int j=0;j<n;j++){
                if((Integer)a.get(j)==nums[j]){
                    if(j==n-1)
                        mark=i;
                    continue;}
                else break;
            }
        }
        if(mark==res.size()-1){
            mark=-1;
        }
        int[] ans=new int[n];int cout=0;
        for(int i:res.get(mark+1)){
            ans[cout++]=i;
        }
        return ans;
    }
}