首页 > 试题广场 >

下一个排列

[编程题]下一个排列
  • 热度指数:2071 时间限制: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

输入

[1,2,3]

输出

[1,3,2]
示例2

输入

[3,2,1]

输出

[1,2,3]

说明

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

输入

[2]

输出

[2]
头像 代码界的小白
发表于 2022-01-03 19:25:54
题目主要信息 1、给出一个数组的排列 2、找到该数组的下一个排列,使得新数组是大于该数组的最小数组 方法一:两次扫描 具体方法 注意到下一个排列总是比当前排列要大,除非该排列已经是最大的排列。我们希望找到一种方法,能够找到一个大于当前序列的新序列,且变大的幅度尽可能小。具体地: 我们需要将一个左边 展开全文
头像 godhands
发表于 2022-01-10 15:08:24
描述 题目描述 首先给定我们一个排列,让我们求出来他的下一个排列是多少,如果当前已经是最大的排列了,我们直接输出最小的排列就可以了 什么是排列的顺序,假设我们从1...n那么我们按照字典序的顺序,构造我们的排列,按位比较小的字典序小,并且排列更小 样例解释 样例输入'[1,2,3]' 这里我们给出我 展开全文
头像 吕芳SG
发表于 2022-01-30 10:42:10
整数数组的一个排列 就是将其所有成员以序列或线性顺序排列。 给你一个整数数组 nums ,找出 nums 的下一个排列。必须原地修改,只允许使用额外常数空间。 下一个排列 按照字典序的下一个更大的排列;若已经是最大值,下一个排列为最小序号 问题分析:元素按升序排列的下一个元素 举例:输入[1,2, 展开全文
头像 CroMarmot
发表于 2022-01-03 08:01:21
题意 求数组的所有排列中,恰好在当前数组排列的下一个的数组 限制: 数组长度不大于1000 方法 性质分析 如果一个数组恰好是另一个数组排列的下一个,那么首先两个数组不等,其次它们有公共前缀,在公共前缀后新数组比原数组大, 新数组剩余部分从小到大排列 正确性证明: 因为是下一个,所以不相等.存在一位 展开全文
头像 hqw11
发表于 2023-02-06 21:46:05
package main import "sort" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return(756076230) int整型一维数组 */ func nextP 展开全文
头像 姐姐的遮阳伞
发表于 2022-03-30 19:42:49
思路: 看注释吧,谢谢,我注释写得很详细,这里就不再重新写了(懒...) import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 展开全文
头像 1813004745
发表于 2022-02-21 18:46:57
我们知道正序是最小的,倒序是最大的。因此我们可以从后往前去找第一个非倒序的值,然后用这个值去跟倒序数里面比它大的第一个数进行交换即可。最后记得反转逆序数组。 特殊情况: 倒序 直接返回正序 size == 1直接返回原数组 import java.util.*; public class Solu 展开全文
头像 牛客327297870号
发表于 2023-03-04 21:20:28
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return(756076230) int整型一维数组 # class Solution: def nextPermutation(self , 展开全文
头像 老舍长
发表于 2024-03-29 15:00:39
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: def nextPermutation(self , nums: List 展开全文
头像 glennbh
发表于 2023-02-02 23:50:46
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return(756076230) int整型一维数组 # class Solution: def nextPermutation(self , 展开全文