凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 60. Permutation Sequence

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


题目

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):

  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.

题意

给出 n 和 k,求出长度为 n 的序列的第 k 个排序。

解法 1

最简单的方法就是调用 k 次 31. Next Permutation 这一题解出的函数。

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 序列为最小序列的情况下)。 因此可以得出如下解法:

ass 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;
    }
};