凌云的博客

LeetCode 算法题 60. 第 k 个排列

分类：algorithm| 发布时间：2017-03-12 22:23:00

---

题目

给出集合 [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"

解法 1

最简单的方法就是调用 k 次 31. 下一个排列 这一题解出的函数。

class Solution {
public:
    string getPermutation(int n, int k) {
        string ret;
        for (int i = 0; i < n; ++i)
            ret += '1' + i;

        while (--k) nextPermutation(ret);
        return ret;
    }

    void nextPermutation(string& nums) {
        if (nums.empty()) return;
        // in reverse order, find the first number which is in increasing trend (we call it violated number here)
        int i;
        for (i = nums.size() - 2; i >= 0; --i) {
            if (nums[i] < nums[i+1]) break;
        }

        // reverse all the numbers after violated number
        reverse(begin(nums)+i+1, end(nums));
        // if violated number not found, because we have reversed the whole array, then we are done!
        if (i == -1) return;
        // else binary search find the first number larger than the violated number
        auto itr = upper_bound(begin(nums)+i+1, end(nums), nums[i]);
        // swap them, done!
        swap(nums[i], *itr);
    }
};

当然这种方法效率极差，并不是最好的方法。

解法 2

通过观察序列可知，假设序列的长度为 n，从左往右数第 i 个数字需要与 i + k / (n - i - 1)! 个数字进行交换（在 i..n 序列为最小序列的情况下）。 因此可以得出如下解法：

class Solution {
public:
    string getPermutation(int n, int k) {
        string ret;
        for (int i = 0; i < n; ++i)
            ret.push_back('1' + i);

        // generate weight array
        vector<int> weights(n, 0);
        for (int i = 1, weight = 1; i < n; ++i, weight = weight * i) {
            weights[n - i - 1] = weight;
        }

        --k;
        for (int i = 0; i < n - 1; ++i) {
            int j = k / weights[i];
            if (!j) continue;
            k -= (j * weights[i]);
            j = i + j;
            char tmp = ret[j];
            // sort nums[i + 1...n] to the minimal
            for (int ii = j - 1; ii >= i; --ii)
                ret[ii + 1] = ret[ii];

            ret[i] = tmp;
        }

        return ret;
    }
};