网站个人备案转企业备案,东凤网站,合肥网络公司,装修公司加盟品牌【题目描述】 给出集合 [1,2,3,...,n]#xff0c;其所有元素共有 n! 种排列。按大小顺序列出所有排列情况#xff0c;并一一标记#xff0c;当 n 3 时, 所有排列如下#xff1a;123 、132 、213 、231、312、…【题目描述】 给出集合 [1,2,3,...,n]其所有元素共有 n! 种排列。按大小顺序列出所有排列情况并一一标记当 n 3 时, 所有排列如下123 、132 、213 、231、312、321。给定 n 和 k返回第 k 个排列。
示例 1 输入n 3, k 3 输出213
示例 2 输入n 4, k 9 输出2314 示例 3 输入n 3, k 1 输出123
提示 11 n 9 21 k n!
【题目链接】. - 力扣LeetCode
【解题代码】 package number;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;public class GetPermutation {public static void main(String[] args) {//int n 4, k 9;int n 4, k 3;System.out.println(计算结果 new GetPermutation().getPermutation(n, k));}public String getPermutation(int n, int k) {// 生成1到n的数组int[] nums IntStream.range(1, n 1).toArray();// 运行K次获取下一个数字排列组合for (int i 0; i k - 1; i) {nextPermutation(nums);}// 最后将生成的整数数组结果转换成字符串return Arrays.stream(nums).mapToObj(String::valueOf).reduce((a, b) - a b).get();}private void nextPermutation(int[] nums) {// 从倒数第二个数开始尝试能够递增替换此数字依次向前推进int i nums.length - 2;Lable:for (; i 0; i--) {// 往后找比当前数大的数将两个数交换然后跳出整个循环for (int j nums.length - 1; j i; j--) {if (nums[i] nums[j]) {int tmp nums[i];nums[i] nums[j];nums[j] tmp;break Lable;}}}// 后面的数字从小到大排序即可Arrays.sort(nums, i 1, nums.length);}}【解题思路】 之前此题已经在博文LeetCode-60题排列序列解法一原创-CSDN博客中介绍了一种解法虽然提交成功但运行时长400多毫秒而且递归实现有些晦涩还有没有其它更加巧妙的方法呢本人苦苦思索拿着数字排列“31243142321432413412。。。“翻来覆去的去找其中的规律突然间真是灵光一闪发现如下真理每个数字排列的下一个排列就是从倒数第二个数字开始往后找到比此数大的数字两者进行交换然后再将后面的数字进行排序即可找不到的话向前推进。。。发现这么大的天机当下真是兴奋不已立马修改好代码运行提交LeetCode成功 【解题步骤】
定义一个递归回溯函数获取输入的数字集合下一个排列 private void nextPermutation(int[] nums) {。。。} 主函数里先初始化数字集合为最小排列序列然后对此数字集合取k-1次下一个排列然后返回结果即可 // 生成1到n的数组
int[] nums IntStream.range(1, n 1).toArray();
// 运行K次获取下一个数字排列组合
for (int i 0; i k - 1; i) {nextPermutation(nums);
}
// 最后将生成的整数数组结果转换成字符串
return Arrays.stream(nums).mapToObj(String::valueOf).reduce((a, b) - a b).get(); nextPermutation函数里i从倒数第二个数开始尝试能够递增替换此数字依次向前推进往后找比当前数大的数将两个数交换然后跳出整个循环 // 已经访问到数字集合尾部当前排列完成生成 序列号加1并返回
if (n nums.length) {return m 1;
} 然后将后面的数字从小到大排序即可 Arrays.sort(nums, i 1, nums.length);
【思考总结】
算法实现精要每个数字排列的下一个排列就是从倒数第二个数字开始往后找到比此数大的数字两者进行交换然后再将后面的数字进行排序即可找不到的话向前推进。。。算法实现最好能精益求精不可浅尝辄止温故而知新比做新的算法题可能收获更大一定要有自己的原创算法思想不能一味按照公式去套那样的话就只是机械的应试刷题没有自己的灵魂没有自己的思想LeetCode解题之前一定不要看题解看了就“破功”了
