P3 第k个排列 LeetCode60

P3第k个排列，难度中等，主要标签为回溯算法。

题目

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

给定 n 和 k，返回第 k 个排列。

说明：

• 给定 n 的范围是 [1, 9]。
• 给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

LeetCode题目链接https://leetcode-cn.com/problems/permutation-sequence/

---

解题思路

解题代码：

class Solution {
    public String getPermutation(int n, int k) {
    	List<Integer> nums = new ArrayList<Integer>();
    	//nums[]存储1，2，3...n，最高位数字
    	for (int i = 0; i < n; i++) {
    		nums.add(i + 1);
    	}
    	return getAns(nums, n, k);
    }
    
    private String getAns(List<Integer> nums, int n, int k) {
    	if (n == 1) {
    		return nums.get(0) + "";  // nums.get(0) 获取数组下标为0的值
    	}
    	int perGroupNum = factorial(n - 1);
    	int groupNum = (k - 1) / perGroupNum;  // 计算第k个数在第几组
    	int num = nums.get(groupNum);  // 获取当前最高位
    	nums.remove(groupNum);  //最高位列表中去除当前最高位数字
    	k = k % perGroupNum;  // 计算余数，即下一组中位置
    	k = (k == 0 ? perGroupNum : k);  //  计算余数为0，则为本组最后的位置，更新k=每组的个数
    	return num + getAns(nums, n-1, k);
    	
    }
    
    // 斐波拉切数列
    public int factorial(int number) {
    	if (number <= 1) {
    		return 1;
    	} else {
    		return number * factorial(number - 1);
    	}
    }
    
}

测试主函数：

import java.util.ArrayList;
import java.util.List;


public class PermutationSequence {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution s = new Solution();
		System.out.print(s.getPermutation(4, 9));
	}

}

输出：

2314

本文作者： Yao Zhu
发布时间： 2019-08-31
最后更新： 2019-09-07
本文链接： https://juoyo.github.io/posts/f46c16da.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信