leetcode 60. Permutation Sequence 第K个全排列

灰太狼 2022-06-09 10:58 152阅读 0赞

The set \[1,2,3,…,n\] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,  
We get the following sequence (ie, for n = 3):

“123”  
“132”  
“213”  
“231”  
“312”  
“321”  
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

这道题是要得到第k个全排列， n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。

代码如下：

public class Solution 
    {
        
        /*
         * n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。
         * 思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，
         * 也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，
         * 得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。
         * */
        public String getPermutation(int n, int k)
        {
            StringBuilder list=new StringBuilder();
            for(int i=1;i<=n;i++)
                list.append(i+"");
    
            StringBuilder res=new StringBuilder();
            int factor=getFactor(n);
            for(int i=n;i>=1;i--)
            {
                factor=factor/i;
                int index=(k-1)/factor ;  //第k个，k是从1开始的，所以要减一，从0开始
                res.append(list.charAt(index));
                list.deleteCharAt(index);
                k=k-index*factor;
            }
            return res.toString();
        }
    
        public int getFactor(int n)
        {
            int sum=1;
            for(int i=1;i<=n;i++)
                sum*=i;
            return sum;
        }
    }

下面是C++的做法，我是网上参考的答案，有点搞不懂

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    
    using namespace std;
    
    class Solution 
    {
    public:
        string getPermutation(int n, int k) 
        {
            string list = "";
            for (int i = 1; i <= n; i++)
                list += to_string(i);
    
            string res;
            int factor = getFector(n);
            for (int i = n; i >= 1; i--)
            {
                factor = factor / i;
                int index = (k - 1) / factor;
                res += list[index];
                k = k - index*factor;
                list.erase(list.begin()+index);
            }
            return res;
        }
    
        int getFector(int n)
        {
            int product = 1;
            for (int i = 1; i <= n; i++)
                product *= i;
            return product;
        }
    };

我的建议是直接使用C++的next\_permutation函数

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        string getPermutation(int n, int k) 
        {
            string res = "";
            for (int i = 1; i <= n; i++)
                res += to_string(i);
    
            int i = 1;
            while (i<k && next_permutation(res.begin(), res.end()))
                i++;
    
            return res;
        }
    };