下一个排列

[编程题]下一个排列

热度指数：2070 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组，将数组重新排列，得到一系列数组排列S，请你从S中，找出恰好比当前数组排列字典序大于1的数组排列。

1.[1,2,3]的得到的数组排列S有:[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]。

2.该题数组排列的字典序大小排序规则：2个数组排列的元素按顺序比较，直到数组元素不相等为止，不相等的第一个元素，谁的元素大，谁的字典序比较大，比如数组a=[1,2,3]与数组b=[1,3,2]比较：a[0]=b[0]，a[1]<b[1]，此时出现了第一个不相同的，且a[1]<b[1]，则a的字典序小于b的字典序。且[1,3,2]的字典序在排列S中，正好在[1,2,3]的后面，视为[1,3,2]的字典序比[1,2,3]的字典序大于1。

3.如果不存在更大的数组排列，则返回最小的数组排列。

数据范围：排列长度满足 $1 \le n \le 1000 \$ ，排列中的值满足 $1 \le val \le 1000 \$

示例1

输入

[1,2,3]

输出

[1,3,2]

示例2

输入

[3,2,1]

输出

[1,2,3]

说明

[3,2,1]是当前最大的数组排列了，不存在比它更大的了，故返回最小的数组排列

示例3

输入

[2]

输出

[2]

算法知识视频讲解

小谷围做题家

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
}

发表于 2023-03-15 00:08:44 回复(0)

hqw11

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
}

发表于 2023-02-06 21:45:26 回复(0)