小旭讲解-LeetCode-60.-Permutation-Sequence-1
小旭讲解-LeetCode-60.-Permutation-Sequence-1

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:

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

Given n and k, return the kth 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"

思路

小旭讲解 LeetCode 60. Permutation Sequence
小旭讲解 LeetCode 60. Permutation Sequence

代码

回溯

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/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。