排列序列

60. 排列序列

难度困难519

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

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

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

给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出："213"

示例 2：

输入：n = 4, k = 9
输出："2314"

示例 3：

输入：n = 3, k = 1
输出："123"

提示：

• 1 <= n <= 9
• 1 <= k <= n!

C++库函数next_permutation

class Solution {
    public String getPermutation(int n, int k) {
        char[]arr = new char[n];
        for(int i=0;i<n;i++){
            arr[i] = (char)('0'+(i+1));
        }
        for(int i=0;i<k-1;i++){
            nextPermutation(arr);
        }
        return String.valueOf(arr);
    }

    public boolean nextPermutation(char[] num) {
        if (num.length <= 1) return false;
        for (int i = num.length - 2; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                int j;
                for (j = num.length - 1; j >= i; j--) {
                    if (num[i] < num[j]) break;
                }
                swap(num, i, j);
                //sort the rest of arrays after the swap point.
                Arrays.sort(num, i + 1, num.length);
                return true;
            }
        }
        //reverse the arrays.
        for (int i = 0; i < num.length / 2; i++) {
            swap(num, i, num.length - i - 1);
        }
        return false;
    }

    public void swap(char[] arr, int index1, int index2) {
        char temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

数学+缩小问题规模

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }

        --k;
        StringBuffer ans = new StringBuffer();
        int[] valid = new int[n + 1];
        Arrays.fill(valid, 1);
        for (int i = 1; i <= n; ++i) {
            int order = k / factorial[n - i] + 1;
            for (int j = 1; j <= n; ++j) {
                order -= valid[j];
                if (order == 0) {
                    ans.append(j);
                    valid[j] = 0;
                    break;
                }
            }
            k %= factorial[n - i];
        }
        return ans.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/permutation-sequence/solution/di-kge-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信