小旭讲解 LeetCode 60. Permutation Sequence

BiliBili

YouTube

原题

中文

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

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

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。

说明

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

英文

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 for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

思路

代码

回溯

class Solution {
private:
    bool helper(vector<int>& vis, vector<int>& result, int& no, int target) {
        if (result.size() == vis.size()) {
            if (++no == target) {
                return true;
            }
            return false;
        }
        
        for (int i = 1; i <= vis.size(); ++i) {
            if (vis[i - 1]) continue;
            vis[i - 1] = 1;
            result.push_back(i);
            bool next = helper(vis, result, no, target);
            if (next) return true;
            result.pop_back();
            vis[i - 1] = 0;
        }
        return false;
    }
public:
    string getPermutation(int n, int k) {
        vector<int> vis(n, 0);
        vector<int> result;
        int no = 0;
        helper(vis, result, no, k);
        string ans;
        for (auto n : result) {
            ans += to_string(n);
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O(n!)$
空间复杂度： $O(n)$

数学

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> fact(1, 1);
        // 0 1 2 3 4  5 6 7 8 9
        // 1 1 2 6 24 ......
        for (int i = 1; i <= 9; ++i) {
            fact.push_back(fact.back() * i);
        }
        
        string nums = "123456789";
        string ans;
        
        while (n > 0) {
            int tmp = (k - 1) / fact[n - 1];
            ans += nums[tmp];
            nums.erase(nums.begin() + tmp);
            k -= tmp * fact[n - 1];
            --n;
        }
        
        return ans;
    }
};

复杂度分析

时间复杂度： $O(n)$
空间复杂度： $O(n)$

参考

原题链接：https://leetcode.com/problems/permutation-sequence/

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/leetcode-60-permutation-sequence/