刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

给定一个正整数n，请将n中的每位数字重新排列并组成一个新数，要求新数的值要小于n，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出-1。

例1：n=312，312中每位上的数字依次是3、1、2，重新排列组成的新数有321、231、213、132、123，新数中小于312的有231、213、132、123，其中符合要求的最大正整数是231；

例2：n=123，123中每位上的数字依次是1、2、3，重新排列组成的新数有312、321、231、213、132，新数中不存在小于123的正整数，故输出-1。

输入描述

输入一个正整数 n (1≤ n <2的63次方)

输出描述

输出一个正整数，表示符合要求的最大正整数


样例输入

312

样例输出

231

使用微信搜索喵呜刷题，轻松应对考试！

答案：

对于给定的正整数n，我们需要找到所有小于n的由n的各位数字重新排列得到的新数中最大的那个。首先，我们需要将n的每一位数字提取出来，并存储在一个数组中。然后，我们可以使用全排列算法生成所有可能的排列。在生成排列时，我们需要维护一个当前排列的整数，并检查它是否小于n。如果找到一个符合条件的排列，我们就更新最大数。如果找不到符合条件的排列，我们输出-1。

解析：

【喵呜刷题小喵解析】：

这个题目的核心思路是使用全排列算法，同时检查每个排列是否满足条件。由于我们需要找到符合条件的最大数，因此我们在生成排列的过程中，每次找到一个符合条件的数，都将其与当前最大数进行比较，如果它比当前最大数大，就更新最大数。

具体来说，我们可以按照以下步骤来解题：

1. 将n的每一位数字提取出来，存储在一个数组中。
2. 使用全排列算法生成所有可能的排列。
3. 对于每个排列，检查它是否小于n，如果小于n，则更新最大数。
4. 如果找不到符合条件的排列，输出-1。

需要注意的是，由于n可能非常大，我们需要使用一种高效的算法来生成排列。一种常用的方法是使用回溯算法，每次从剩下的数字中选择一个数字，然后递归地生成剩余数字的排列。这样可以保证生成的排列是完整的，并且不会重复生成相同的排列。

另外，由于n可能非常大，我们需要使用一种高效的方式来比较两个数的大小。一种常用的方法是使用字符串比较，将两个数转换为字符串，然后比较它们的字典序大小。这样可以避免使用乘法和除法运算，从而提高效率。
创作类型：
原创

本文链接：给定一个正整数n，请将n中的每位数字重新排列并组成一个新数，要求新数的值要小于n，请找出所有符合要求

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share